Project Euler 725

题目

Digit sum numbers

A number where one digit is the sum of the other digits is called a digit sum number or DS-number for short. For example, \(352, 3003\) and \(32812\) are DS-numbers.

We define \(S(n)\) to be the sum of all DS-numbers of \(n\) digits or less.

You are given \(S(3) = 63270\) and \(S(7) = 85499991450\).

Find \(S(2020)\). Give your answer modulo \(10^{16}\).

解决方案

令\(N=2020.\)一个数如果是DS数，那么它的数位和是最大数位的\(2\)倍。这不难想到使用动态规划来做。

本题的动态规划过程考虑使用“我为人人”的方法，因为本质上都是对当前状态的所有数都添加一个新的数位\(d\)，从而到达下一个状态。

令状态\(c(i,t,m)(1\le i\le N,0\le t\le18,0\le m\le9)\)表示当前有多少个\(i\)位有前导0的数，其中数位之和为\(t\)，并且这\(i\)个数位中最大数位为\(m.\)

不难知道，对于初值\(i=1,0\le j\le 9\)，都有\(c(i,j,j)=1.\)

考虑对\(c(i,t,m)\)中的所有数后面都拼接一个新的数位\(0\le d\le 9\)，那么可以进行转移：

\(c(i,t,m)\rightarrow c(i+1,t+d,\max(m,d))\)

添加一个数位\(d\)后，那么数位和就变成了\(t+d\)，最大数位也变成了\(\max(m,d).\)

令状态\(s(i,t,m)(1\le i\le N,0\le t\le18,0\le m\le9)\)表示\(i\)位有前导0并满足以下条件的所有数之和：数位之和为\(t\)，并且这\(i\)个数位中最大数位为\(m.\)

同样不难知道，对于初值\(i=1,0\le j\le 9\)，都有\(s(i,j,j)=j.\)

考虑对\(s(i,t,m)\)中的所有数后面都拼接一个新的数位\(0\le d\le 9\)，那么可以进行转移：

\(10s(i,t,m)+d\cdot c(i,t,m)\rightarrow s(i+1,t+d,\max(m,d))\)

添加一个数位\(d\)后，相当于将\(s(i,t,m)\)中的所有数都乘\(10\)，并且每一个数都多了一个数位\(d\)，一共有\(c(i,t,m)\)个。

那么，题目最终所需要求的答案为：

\[\sum_{d=0}^9s(N,2d,d)\]

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2020;
const int B=9,D=2*B;
ll mod=1e16;
ll c[N+1][D+1][B+1],s[N+1][D+1][B+1];
void add(ll &x,ll y){
    x=(x+y)%mod;
}
int main(){
    for(int j=0;j<=B;j++){
        c[1][j][j]=1;
        s[1][j][j]=j;
    }
    for(int i=1;i<N;i++)
        for(int t=0;t<=D;t++)
            for(int m=0;m<=B;m++)
                for(int d=0;d<=B&&t+d<=D;d++){
                    add(c[i+1][t+d][max(d,m)],c[i][t][m]);
                    add(s[i+1][t+d][max(d,m)],s[i][t][m]*10+c[i][t][m]*d);
                }
    ll ans=0;
    for(int j=0;j<=B;j++)
        add(ans,s[N][j+j][j]);
    printf("%lld\n",ans);
}