Project Euler 290
题目
Digital Signature
How many integers have the property that the sum of the digits of equals the sum of digits of ?
解决方案
令 ,考虑使用动态规划解决本题。基本思想是:从低位到高位给 填上数位。因为只要低位先填好了,无论是 还是 ,高位填的数不影响低位的数位和。令 表示数字 的低 位和, 表示数字 的数位和。本题的动态规划过程考虑使用 “我为人人” 的方法,因为本质上都是对当前状态的所有数都添加一个新的数位 ,从而到达下一个状态。
令状态 表示满足如下条件的填法数量:
- 当前已经填充了低 个数位;
- 其 的倍数仍在高位产生了 的进位;
- 已经填入的低 位,其 倍的低 位数位和与自身的数位和之差,也就是 。
那么当 时,。其余 时的情况为 。
考虑对 中的所有数的第 位都拼接一个新的数位 ,那么可以进行转移:
原来的进位 再加上当前的 后,其十位以上的数位变成了新的进位;而其个位则为当前数位。对于新数, 增加了一个数位 ,而 增加了一个数位 ,因此有如此转移过程。
对于终点状态 ,由于进位 还没算上,因此仍然需要补上这些进位的数位之和再进行判断。因此最终答案为
代码
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
| #include <bits/stdc++.h> using namespace std; typedef long long ll;
const int N=18,M=137; const int B= M*(2+log10(M)); ll f[N+1][M][B+B]; int main(){ f[0][0][B] = 1; for(int i=0;i<N;i++) for(int c=0;c<M;c++) for(int s=0;s<B+B;s++){ if(f[i][c][s]==0) continue; for(int d = 0;d < 10;d++){ int nc = (c+d*M)/10; int ns = s+(c+d*M)%10-d; f[i+1][nc][ns]+=f[i][c][s]; } } ll ans=0; for(int c=0;c<M;c++){ int ds=0; for(int t=c;t;t/=10) ds+=t%10; ans+=f[N][c][B-ds]; } printf("%lld\n",ans); }
|