Project Euler 290

Project Euler 290

题目

Digital Signature

How many integers 0n<1018 have the property that the sum of the digits of n equals the sum of digits of 137n?

解决方案

N=18,M=137,考虑使用动态规划解决本题。基本思想是:从低位到高位给 n 填上数位。因为只要低位先填好了,无论是 n 还是 Mn,高位填的数不影响低位的数位和。令 d(n,m) 表示数字 n 的低 m 位和,d(n) 表示数字 n 的数位和。本题的动态规划过程考虑使用 “我为人人” 的方法,因为本质上都是对当前状态的所有数都添加一个新的数位 d,从而到达下一个状态。

令状态 f(i,c,s)(i<N,c<M) 表示满足如下条件的填法数量:

  • 当前已经填充了低 i 个数位;
  • M 的倍数仍在高位产生了 c 的进位;
  • 已经填入的低 i 位,其 M 倍的低 k 位数位和与自身的数位和之差,也就是 s=d(Mn,k)d(n,k)

那么当 i=0 时,f(0,0,0)=1。其余 i=0 时的情况为 0

考虑对 f(i,c,s) 中的所有数的第 i+1 位都拼接一个新的数位 0d9,那么可以进行转移:

c(i,c,s)c(i+1,(c+Md)/10,s+(c+Md)%10d)

原来的进位 c 再加上当前的 Md 后,其十位以上的数位变成了新的进位;而其个位则为当前数位。对于新数,Mn 增加了一个数位 (c+Md)%10,而 n 增加了一个数位 d,因此有如此转移过程。

对于终点状态 f(N,,),由于进位 c 还没算上,因此仍然需要补上这些进位的数位之和再进行判断。因此最终答案为

c=0M1f(N,c,d(c))

代码

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);
}