【CF1513C】Add One(动态规划)

发布时间 2023-09-11 10:02:57作者: Alric

题目大意:

\(n()\)的每个数码加一,重复\(m(1\le m\le 2\times 10^5)\)次,求最终结果的长度,询问\(t(1\le \times)\)次。


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll m,dp[200000+20];
char n[20],nlen;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	for(ll i=0;i<=200000+10;i++){
		if(i<=9)dp[i]=1;
		else if(i==10)dp[i]=2;
		else dp[i]=(dp[i-9]+dp[i-10])%mod;
	}
	while(T--){
		ll ans=0;
		cin >> (n+1) >> m;
		nlen=strlen(n+1);
		for(ll i=1;i<=nlen;i++){
			ans+=dp[m+(n[i]-'0')];
			ans%=mod;
		}
		cout << ans << endl;
	}
	return 0;
}