西安建設(shè)工程信息平臺網(wǎng)絡(luò)優(yōu)化工程師為什么都說坑人
Problem - 1513C - Codeforces
?解析：
? ? ? ? 考慮DP，DP[ i ] 為從 0 開始執(zhí)行 i 次操作，此時數(shù)字的位數(shù)。
? ? ? ? 我們發(fā)現(xiàn)當(dāng)一個9再操作一次就會變成1和0，并且相鄰的大部分長度都不會變化，0會影響10次操作之后的位數(shù)，1會影響9次操作后的位數(shù)。
? ? ? ? 所以，DP[ i ] =?DP[ i - 10 ] +?DP[ i - 9 ]
? ? ? ? 預(yù)處理打表，每次遍歷 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;
}