题目地址：HDU 4389 第一次遇到需要先枚举然后再数位DP的。 先枚举各位数之和，即，1~81，然后数位DP过程中再判断枚举的各位数之和与枚举的数是否相同，只有相同的才算。 dp[i][j][k][h]表示第i位上，当前的各位数和为j，，枚举的各位数和为k，当前的数对k取模为h的数的个数。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=200000+10;int dp[11][82][82][82], dig[11];int dfs(int cnt, int sum, int mods, int res, int maxd){if(cnt==-1) return sum==mods&&res==0;if(sum>mods) return 0;if(maxd&&dp[cnt][sum][mods][res]!=-1) return dp[cnt][sum][mods][res];int i, r=maxd?9:dig[cnt], ans=0;for(i=0;i<=r;i++){ans+=dfs(cnt-1,sum+i,mods,(res*10+i)%mods,maxd||i<r);}if(maxd) dp[cnt][sum][mods][res]=ans;return ans;}int Cal(int x){int i, cnt=0, ans=0;while(x){dig[cnt++]=x%10;x/=10;}for(i=1;i<=81;i++){ans+=dfs(cnt-1,0,i,0,0);}return ans;}int main(){int t, l, r, Case=0;memset(dp,-1,sizeof(dp));scanf(“%d”,&t);while(t–){scanf(“%d%d”,&l,&r);printf(“Case %d: %d\n”,++Case,Cal(r)-Cal(l-1));}return 0;}
喜欢真实的人，要做真实的人，所以从来不会想要刻意模仿任何人。
