[关闭]
@ysner 2018-11-06T19:30:27.000000Z 字数 1114 阅读 1903

[AHOI2009]同类分布

数位DP DP


题面

给出两个数,求出中各位数字之和能整除原数的数的个数。

解析

从原数入手肯定会
换一个角度。
各位数字之和实际上最多只有种。
所以我们可以枚举各位数字之和
然后再转移一下每位填哪个数就完事了。
具体来说,设状态表示到了第位,数字和为,目前凑出的数除的余数为,是否小于上界的方案数。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. ll l,r,f[20][200][200][2],a[20];
  14. il ll gi()
  15. {
  16. re ll x=0,t=1;
  17. re char ch=getchar();
  18. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  19. if(ch=='-') t=-1,ch=getchar();
  20. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  21. return x*t;
  22. }
  23. il ll calc(re ll x)
  24. {
  25. re ll gu=x,tot=0,s=0;
  26. while(gu)
  27. {
  28. a[++tot]=gu%10;
  29. gu/=10;
  30. }
  31. reverse(a+1,a+1+tot);
  32. fp(p,1,9*tot)
  33. {
  34. memset(f,0,sizeof(f));f[0][0][0][0]=1;
  35. fp(i,1,tot)
  36. fp(j,0,p)
  37. fp(k,0,p-1)
  38. fp(l,0,9)
  39. {
  40. if(j+l>p) break;
  41. f[i][j+l][(k*10+l)%p][1]+=f[i-1][j][k][1];
  42. if(l<a[i]) f[i][j+l][(k*10+l)%p][1]+=f[i-1][j][k][0];
  43. if(l==a[i]) f[i][j+l][(k*10+l)%p][0]+=f[i-1][j][k][0];
  44. }
  45. s+=f[tot][p][0][0]+f[tot][p][0][1];
  46. }
  47. return s;
  48. }
  49. int main()
  50. {
  51. l=gi();r=gi();
  52. printf("%lld\n",calc(r)-calc(l-1));
  53. return 0;
  54. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注