1600*C. Add One（数位DP找规律）

Problem - 1513C - Codeforces

 解析：

        考虑DP，DP[ i ] 为从 0 开始执行 i 次操作，此时数字的位数。

        我们发现当一个9再操作一次就会变成1和0，并且相邻的大部分长度都不会变化，0会影响10次操作之后的位数，1会影响9次操作后的位数。

        所以，DP[ i ] = DP[ i - 10 ] + DP[ i - 9 ]

        预处理打表，每次遍历 n 的每一位，然后查询即可。

        注意取模。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+100,mod=1e9+7;
int t,n,m,dp[N];
signed main(){for(int i=0;i<=9;i++) dp[i]=1;for(int i=10;i<=2e5+10;i++) dp[i]=(dp[i-9]+dp[i-10])%mod;scanf("%lld",&t);while(t--){scanf("%lld%lld",&n,&m);int res=0;while(n){res+=dp[n%10+m];res%=mod;n/=10;}printf("%lld\n",res%mod);}return 0;
}