P14337 [JOI2020 预选赛 R2] 求和 / Digit Sum

Giorno_ · 2025-10-28 20:00:21 · 题解

定义 f_x 为有多少个数经过若干次操作可以变成 x，而我们的 f_x 没有算上 x 本身（不进行操作的情况），因此最终答案为 f_x + 1 。
设一个数 a 经过操作后可以得到数 b，得到转移方程：f_b = f_b + f_a + 1。对于每个 b，若其大于 n，那么统计它也没有意义，可以加特判跳过。

代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 1e6 + 10;
int n;
int f[N];
inline int add(int k){
    int cnt = 0;
    while(k){
        cnt += k % 10;
        k /= 10;
    }
    return cnt;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++){
        if(i + add(i) > n)continue;
        f[i + add(i)] += f[i] + 1;
    }
    cout << f[n] + 1;
    return 0; 
}