当前位置:网站首页>Luogu p4127 [ahoi2009] similar distribution problem solution
Luogu p4127 [ahoi2009] similar distribution problem solution
2022-07-06 07:29:00 【q779】
Luogu P4127 [AHOI2009] The same kind of distribution Answer key
Topic link :P4127 [AHOI2009] The same kind of distribution
The question :
Give two numbers a , b a,b a,b , Find out [ a , b ] [a,b] [a,b] The sum of the numbers in can divide the number of the original number .
For all the data , 1 ≤ a ≤ b ≤ 1 0 18 1 ≤ a ≤ b ≤ 10^{18} 1≤a≤b≤1018.
Tomorrow is the final exam, not only do not review, but also brush questions qwqqwqwq
Because we can't know the digit sum of each number exactly
But we know they must be [ 1 , 9 × l ] [1,9 \times l] [1,9×l] Within the scope of ( l l l Is the longest digit )
We enumerate all digit sums and calculate each digit and the corresponding answer
Add up these answers to [ 0 , x ] [0,x] [0,x] The answer
[ a , b ] [a,b] [a,b] The answer of can be split into two questions [ 0 , b ] [0,b] [0,b] and [ 0 , a − 1 ] [0,a-1] [0,a−1]
And here a , b ≤ 1 0 18 a,b \le 10^{18} a,b≤1018 , The direct press in state is obviously unacceptable
So we can consider recording the digits of the current enumeration and the numbers in the sense
Convenience , We call the sum of digits of the current enumeration m m m
set up f i , j , k f_{i,j,k} fi,j,k It means that only the former i i i digit ( Including leading zeros ), front i i i The sum of digits is j j j , Current digital analog m m m by k k k The answer is
It's not hard to find out
f i , j , k = ∑ 0 ≤ d ≤ t f i + 1 , j + d , ( k × 10 + d m o d m ) f_{i,j,k} = \sum_{0 \le d \le t} f_{i+1,j+d,\left(k\times 10 + d \, \bmod \, m\right)} fi,j,k=0≤d≤t∑fi+1,j+d,(k×10+dmodm)
among t t t For the first time i + 1 i+1 i+1 High bit limit
The search and writing method can be much simpler
Time complexity O ( 9 3 × l 4 ) O(9^3\times l^4) O(93×l4)
Code :
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()
int len,num[25],f[25][205][205];
int dfs(int u,int sum,int st,int limit,int p)
{
if(u>len)
{
if(!sum)return 0;
return st==0&&sum==p;
}
if(!limit&&f[u][sum][st]!=INF)
return f[u][sum][st];
int up=limit?num[len-u+1]:9;
int res=0;
for(int i=0; i<=up; i++)
res+=dfs(u+1,sum+i,(10*st+i)%p,limit&&i==up,p);
return limit?res:f[u][sum][st]=res;
}
int solve(int x)
{
int res=0; len=0;
while(x) num[++len]=x%10,x/=10;
for(int m=1; m<=9*len; m++)
{
memset(f,0x3f,sizeof(f));
res+=dfs(1,0,0,1,m);
}
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int l,r; cin >> l >> r;
cout << solve(r)-solve(l-1) << '\n';
return 0;
}
It's okay anyway whk For the time being
Reprint please explain the source
边栏推荐
- 可变参数重载时的内存错误
- Simple and understandable high-precision addition in C language
- Full Score composition generator: living on code
- Oracle column to row -- a field is converted to multiple rows according to the specified separator
- leecode-C語言實現-15. 三數之和------思路待改進版
- How to delete all the words before or after a symbol in word
- 【JDBC】快速入门教程
- TS类型体操 之 字符串的妙用
- 杰理之如若需要大包发送,需要手机端修改 MTU【篇】
- #systemverilog# 可综合模型的结构总结
猜你喜欢
NiO programming introduction
Simulation of Michelson interferometer based on MATLAB
杰理之BLE【篇】
Twelve rules for naming variables
Google可能在春节后回归中国市场。
(4) Web security | penetration testing | network security web site source code and related analysis
Ali's redis interview question is too difficult, isn't it? I was pressed on the ground and rubbed
烧录场景下的源代码防泄密方案分享
How to delete all the words before or after a symbol in word
Oracle column to row -- a field is converted to multiple rows according to the specified separator
随机推荐
Simple and understandable high-precision addition in C language
Select all the lines with a symbol in word and change them to titles
The best way to learn SEO: search engine
洛谷P1836 数页码 题解
杰理之AD 系列 MIDI 功能说明【篇】
NiO programming introduction
Relevant introduction of clip image
[CF Gym101196-I] Waif Until Dark 网络最大流
【mysql学习笔记30】锁(非教程)
TypeScript 函数定义
Full Score composition generator: living on code
Excel的相关操作
[MySQL learning notes 30] lock (non tutorial)
可变参数重载时的内存错误
jmeter性能测试步骤实战教程
GET/POST/PUT/PATCH/DELETE含义
[MySQL learning notes 32] mvcc
qt颜色与字符串、uint相互转换
C # connect to SQLite database to read content
If Jerry needs to send a large package, he needs to modify the MTU on the mobile terminal [article]