CF1513C题解

一道递推

由于对于一个数 x ,可得 x+10-x=10（废话） 于是问题就变成了 0+m 次,然后 x+m 就变成 0+x+m （还是废话） 于是可以写一个递推。

首先对于函数 f(m) 可分为 m ≤ 9 和 m>9 ,然后可得出递推式结果为 1 或 f(m-9)+f(m-10) ，所以我们可以直接求出结果再分解数位求值。

最后贴上代码

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int Maxn = 2e5 + 11, mod = 1e9 + 7;
 5 int a[Maxn], n, m, t, cnt;//因为每次都%了，可不开long long
 6 int main() {
 7   ios::sync_with_stdio(false);//必须优化（卡读入）
 8   cin.tie(0);
 9   for (int i = 0; i < Maxn; i++) {
10     a[i] = i < 10 ? 1 : (a[i - 9] + a[i - 10]) % mod;//递归求值
11   }
12   for (cin >> t; t; t--) {
13     cnt = 0;
14     for (cin >> n >> m; n; n /= 10) {
15       cnt = (cnt + a[n % 10 + m]) % mod;//分解数位计算
16     }
17     cout << cnt << '\n';
18   }
19   return 0;//华丽的结束
20 }