CF1513C.Add One

题目：

分析：记忆化搜索，9的贡献为两部分。

 1 #include 
 2 using namespace std;
 3 int n, m;
 4 const int mod = 1e9+7;
 5 vectorint>>f;
 6 
 7 int dp(int d, int m){
 8     if(!m) return 1;
 9     if(~f[d][m]) return f[d][m];
10     int res = 0;
11     if(d==9){
12         res=(dp(1, m-1)+dp(0, m-1))%mod;
13     }else{
14         res=dp(d+1, m-1);
15     }
16     return f[d][m] = res;
17 }
18 
19 int main(void){
20     ios::sync_with_stdio(false);
21     cin.tie(0);
22     int T;
23     cin>>T;
24     f.resize(10, vector<int>(2e5+1, -1));
25     for(int i=0; i<10; i++)dp(i, 2e5);
26     while(T--){
27         cin>>n>>m;
28         int res = 0;
29         while(n){
30             (res+=f[n%10][m])%=mod;
31             n/=10;
32         }
33         cout<'\n';
34     }
35     return 0;
36 }