Project Euler 290

发表于 更新于 分类于 本文字数： 903 阅读时长 ≈ 1 分钟

Project Euler 290

题目

Digital Signature

How many integers 0≤n<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 位都拼接一个新的数位 0≤d≤9，那么可以进行转移：

c(i,c,s)→c(i+1,⌊(c+Md)/10⌋,s+(c+Md)%10−d)

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

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

∑c=0M−1f(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);
}