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;
}