@ysner
2018-11-06T19:30:27.000000Z
字数 1114
阅读 1903
数位DP
DP
给出两个数,求出中各位数字之和能整除原数的数的个数。
从原数入手肯定会。
换一个角度。
各位数字之和实际上最多只有种。
所以我们可以枚举各位数字之和。
然后再转移一下每位填哪个数就完事了。
具体来说,设状态表示到了第位,数字和为,目前凑出的数除的余数为,是否小于上界的方案数。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
ll l,r,f[20][200][200][2],a[20];
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il ll calc(re ll x)
{
re ll gu=x,tot=0,s=0;
while(gu)
{
a[++tot]=gu%10;
gu/=10;
}
reverse(a+1,a+1+tot);
fp(p,1,9*tot)
{
memset(f,0,sizeof(f));f[0][0][0][0]=1;
fp(i,1,tot)
fp(j,0,p)
fp(k,0,p-1)
fp(l,0,9)
{
if(j+l>p) break;
f[i][j+l][(k*10+l)%p][1]+=f[i-1][j][k][1];
if(l<a[i]) f[i][j+l][(k*10+l)%p][1]+=f[i-1][j][k][0];
if(l==a[i]) f[i][j+l][(k*10+l)%p][0]+=f[i-1][j][k][0];
}
s+=f[tot][p][0][0]+f[tot][p][0][1];
}
return s;
}
int main()
{
l=gi();r=gi();
printf("%lld\n",calc(r)-calc(l-1));
return 0;
}