S - Digit Sum
原题链接:https://atcoder.jp/contests/dp/tasks/dp_s
题目大意:
给一个n,求从1到n的数中,所有位上的数字之和能被m整除的个数。
解题思路:
数位$dp$,建一个三维数组,$dp[i][j][k]$,其中,$i$代表第几位,j代表位数前i位位数之和对$m$取余的结果,$k$代表前i位是否已经是最大的数,如果已经是最大的,那$i+1$位就从$0$遍历到$n[i+1]$,否则就遍历到9。然后记忆化搜索。
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define debug(a) cout<<#a<<":"<<a<<endl; 5 const ll INF=0x3f3f3f3f; 6 const ll N=1e6+7; 7 const ll mod=1e9+7; 8 ll maxn,minn; 9 ll T,n,m,k; 10 string s; 11 ll arr[N]; 12 ll dp[10010][110][2]; 13 14 ll dfs(ll a,ll b,ll c){ 15 ll d,ans=0,bb; 16 if(dp[a][b][c]!=-1){ 17 return dp[a][b][c]; 18 } 19 if(a==n+1){ 20 if(b==0){ 21 return dp[a][b][c]=1; 22 } 23 else{ 24 return dp[a][b][c]=0; 25 } 26 } 27 if(c==1){ 28 d=arr[a]; 29 } 30 else{ 31 d=9; 32 } 33 for(ll i=0;i<=d;i++){ 34 bb=(b+i)%k; 35 dp[a+1][bb][c&(i==d)]=dfs(a+1,bb,c&(i==d)); 36 ans=(ans+dp[a+1][bb][c&(i==d)])%mod; 37 } 38 return dp[a][b][c]=ans; 39 } 40 41 int main(){ 42 cin>>s>>k; 43 n=s.size(); 44 for(ll i=1;i<=n;i++){ 45 arr[i]=s[i-1]-'0'; 46 } 47 memset(dp,-1,sizeof(dp)); 48 49 printf("%lld\n",(dfs(1,0,1)-1+mod)%mod); 50 51 return 0; 52 }