This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

Codeforces is an interesting question to write today.Codeforces 1513 c plus one:

Given a string of numbers NNN, each operation requires adding one to each digit. The number 111 becomes 222. , the number 999 becomes 101010. For example, 191219121912 becomes 210232102321023. The following operations should also follow this rule.

Input: The first line is the test sample number TTT.

The TTT lines that follow each line contain an initial number NNN and an operation step MMM.

Output: You need to mod(1e9+7) mod\,(1e9 +7)mod (1e9+7)mod (1e9+7)mod (1e9+7) for each sample output.

Ii. Analysis of Ideas:

A simple analysis shows that the numbers [0…9][0…9] will become 101010 after enough steps, and then the problem becomes two smaller ones: how many bits will 111 and 000 become after the remaining steps.

We can use f(I,m)f(I,m)f(I,m)f(I,m), I ∈[0,9] I \in [0,9] I ∈[0,9] I to express the length of iii after steps 10− I10-I10 − I. It is easy to see that III will become 101010 after steps 10− I10 − I. So the following situation is simply equivalent to what the total lengths of 111 and 000 are after the m−(10− I)m – (10 – I)m−(10− I) steps.

So there are f (I, m) = {1, m < 10 – the if (1, m – 10 + I) + f (0, 10 + m – I), 10 m or more – the if (I, m) = \ begin {cases} 1, 10 – I \ \ \ < quad m f (1, m – 10 + I) + f (0, M – 10 + I), 10 – I \ \ \ geq quad m end {cases} f (I, m) = {1, m < 10 – the if (1, m – 10 + I) + f (0, 10 + m – I), 10 – I m or higher

So if you look at this, and you already know how to write it, you’re going to preprocess a two-dimensional array of values for f(I,m)f(I,m)f(I,m) that you might use, and that’s the two-dimensional DP. But by doing that we can optimize it to one dimension.

Let dp[j]dp[j]dp[j] represent the length of 000 after the JJJ step, because ∀ K ∈[0,9]\forall K \in [0,9] ∀ K ∈[0,9] any of it can be regarded as JJJ generated after KKK steps, So f (I, m) = dp/I + m f (I, m) = dp/I + m f (I, m) = dp (I + m).

Let j=m+ij =m+ij =m+ I, combined with the above derivation, we can get: Dp [I] = {1, I < 10 dp [I – 9] + dp [10] – I, I 10 or more dp = \ [I] the begin cases in 1, and attach \ quad I < 10 \ \ dp [9] I – + dp [10] I -, \ quad 10 \ \ geq end I {cases} dp [I] = {1, I < 10 dp [I] – 9 + dp [10] – I, I 10 or more

Iii. AC Code:

#include <iostream>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 50;
const int mod = 1e9 + 7;

int dp[maxn];

void getDp(a) {
    for (int i = 0; i < 10; ++i) {
        dp[i] = 1;
    }
    for (int i = 10; i < maxn; ++i) {
        dp[i] = (dp[i - 10] + dp[i - 9]) % mod; }}void solve(a) {

    int n, m;
    cin >> n >> m;
    int ans = 0;
    while (n) {
        ans = ((ll)ans + dp[n % 10 + m]) % mod;
        n /= 10;
    }

    printf("%d\n", ans);
}

int main(a) {
    
    // The synchronous stream must be turned off or CIN will time out
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    getDp(a);int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
Copy the code

Iv. Summary:

The first thing that came to my mind when I was writing this problem was the backward recursion, and the difference between the DP and the end point is that one goes forward, and the other goes back from 000. The idea of both of these is to break down a big problem into smaller problems, which is divide and conquer, which again illustrates the importance of the basic idea. Simple recursions can cause stack overflows, and interested students can try to write recursions using mnemonic search optimization, but that’s another story.