ICPC 2019 Hong Kong J（数位dp）

[题目链接](https://vjudge.net/problem/Gym-102452J) ------------ ------------ ```cpp #include <bits/stdc++.h> using namespace std; const int M=5e3+5,N=64,mod=1e9+7; int dp[M][N][N],b[M],p[M],m; char R[M],L[M]; int dfs(int pos,int lim,int sum,int num) { if(!pos)return !num; if(!lim&&dp[pos][sum][num]!=-1)return dp[pos][sum][num]; int upn=(lim?b[pos]:9); int ans=0; for(int i=0;i<=upn;i++) ans=(ans+dfs(pos-1,lim&&i==upn,(sum+i)%m,(num+sum*i%m-i*p[pos-1]%m+m)%m))%mod; if(!lim)dp[pos][sum][num]=ans; return ans; } int solve(char *s,int len) { for(int i=1;i<=len;i++)b[i]=s[len-i+1]-'0'; for(int i=1;i<=len;i++)for(int j=0;j<m;j++)for(int k=0;k<m;k++)dp[i][j][k]=-1; return dfs(len,1,0,0); } int main() { int T;scanf("%d",&T); while(T--) { scanf("%s%s%d",L+1,R+1,&m); int len1=strlen(L+1); int len2=strlen(R+1); p[0]=1; for(int i=1;i<=max(len1,len2);i++)p[i]=p[i-1]*10%m; L[len1]--; for(int i=len1;i>=1;i--)if(L[i]>='0')break;else L[i]='9',L[i-1]--; int ans=(solve(R,len2)-solve(L,len1)+mod)%mod; printf("%d\n",ans); } return 0; } ```