C. Add One (Divide by Zero 2021 and Codeforces Round #714 (Div. 2))

問題

https://codeforces.com/contest/1513/problem/C

問題概要

整数nとmが与えられる。nの各桁の数に1を加えたものを並べた列を新しいnに置き換える操作をm回繰り返したとき、nが何桁になっているか答えよ。

考察

とりあえず0からスタートしてどうなるか見てみます。

数	桁数
0	1
1	1
2	1
3	1
4	1
5	1
6	1
7	1
8	1
9	1
10	2
21	2
32	2
43	2
54	2
65	2
76	2
87	2
98	2
109	3
2110	4
3221	4

桁数の列をOEISにぶち込んでみます。

A103377 - OEIS

なんと、ありました。というわけで、ここで示された漸化式「n < 10のときa(n) = 1, n>=10のときa(n) = a(n - 9) + a(n - 10)」でmの制約である2*10^5+10ほどを前計算しておき、nの各桁の数d_iに対してa(m + d_i)を求めて合算したものが答えです。

しかし、i番目の数がi-9番目とi-10番目の数を連結してできるというのは（並べてみれば）分かるのですが、なぜそうなるのかはわかりません。（おい

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
 
int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> f(200020);
    for (int i = 0; i < 10; i++) f[i] = 1;
    for (int i = 10; i < 200020; i++) {
        f[i] = f[i - 9] + f[i - 10];
        f[i] %= MOD;
    }

    int t;
    cin >> t;
    while (t--) {
        string s;
        int m;
        cin >> s >> m;
        int ans = 0;
        for (char c : s) {
            ans += f[m + (int)(c - '0')];
            ans %= MOD;
        }
        cout << ans << endl;
    }
}