C/C++教程

CF1513C.Add One

本文主要是介绍CF1513C.Add One,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

分析:记忆化搜索,9的贡献为两部分。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 const int mod = 1e9+7;
 5 vector<vector<int>>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<<res<<'\n';
34     }
35     return 0;
36 }

 

这篇关于CF1513C.Add One的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!