Project Euler 290

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

Project Euler 290

题目

Digital Signature

How many integers \(0 \le n < 10^{18}\) 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\le d\le 9\)，那么可以进行转移：

\(c(i,c,s)\rightarrow c(i+1,\lfloor(c+Md)/10\rfloor,s+(c+Md)\%10-d)\)

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

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

\[\sum_{c=0}^{M-1} f(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);
}