BZOJ-1799


题目地址:点此传送
题目
Problem Description

给出a,b,求出[a,b]中各位数字之和能整除原数的数的个数。

input

Output

Sample Input

10 19

Sample Output

3

HINT

【约束条件】$1\leq a\leq b\leq10^{18}$

题意

看题(略)

思路

数位dp,我感觉很暴力,但是自己不会….
dp[pos][sum][val],其中pos代表第几位,sum是剩下位数需要凑够的数,val是现在模mod后剩下的值,为什么说暴力呢? 这道题就是暴力枚举所以可能出现的位数和,也就是mod,每次换一个mod就得清一次dp(没办法dp没办法再开mod大了),所以我感觉还是有点暴力的……

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e4 + 10;
ll dp[20][200][200];
ll d[20];
ll dfs(int pos,int sum,int val,int mod,int limit){

if(sum-pos*9-9>0) return 0;
if(pos<0) return sum==0&&val==0;
if(sum<0) return 0;
if(!limit&&dp[pos][sum][val]!=-1) return dp[pos][sum][val];
ll ans=0;
ll end=limit?d[pos]:9;
for(int i=0;i<=end;i++){

if(sum-i>=0){
ans+=dfs(pos-1,sum-i,(val*10+i)%mod,mod,limit&(i==end));
}

}
if(!limit)
dp[pos][sum][val]=ans;

return ans;



}
ll solve(ll x){
ll cnt=0;
ll ans=0;
while(x){

d[cnt++]=x%10;
x/=10;

}
for(int i=1;i<=cnt*9;i++){
memset(dp,-1,sizeof(dp));
ans+=dfs(cnt-1,i,0,i,1);
}

return ans;

}
int main()
{

ll a,b;
scanf("%lld%lld",&a,&b);
printf("%lld\n",solve(b)-solve(a-1));
return 0;
}
如果对您有帮助,请小小支持一下,您的支持将鼓励我继续创作!
0%