hdu 4389 数位DP

 1 /*
 2 查询一段区间，有多少能被它各个数位之和整除的个数
 3 */
 4 #include <iostream>
 5 #include <cstdio>
 6 #include <cstring>
 7 using namespace std;
 8 
 9 int dp[11][82][82][82];//分别表示第i位,前缀数字各个和j,模k,余x
10 int digit[11];
11 
12 int dfs(int pos,int sum,int mod,int res,int limit)
13 {
14     if(pos<=0) return mod==sum && res==0;//数字各个位之和一致且模mod为0
15     if(sum>mod) return 0;//若前缀各个位之和大于mod,则不符合条件了
16     if(!limit && dp[pos][sum][mod][res]!=-1)
17         return dp[pos][sum][mod][res];
18     int ans=0;
19     int end=limit?digit[pos]:9;
20     for(int i=0;i<=end;i++)
21         ans+=dfs(pos-1,sum+i,mod,(res*10+i)%mod,limit&&(i==end));
22     if(!limit) dp[pos][sum][mod][res]=ans;
23     return ans;
24 }
25 int solve(int n)
26 {
27     int pos=0;
28     while(n)
29     {
30         digit[++pos]=n%10;
31         n/=10;
32     }
33     int ans=0;
34     for(int i=1;i<=81;i++)//枚举mod的值
35         ans+=dfs(pos,0,i,0,1);
36     return ans;
37 }
38 int main()
39 {
40     memset(dp,-1,sizeof(dp));
41     int t,icase=0,a,b;
42     scanf("%d",&t);
43     while(t--)
44     {
45         scanf("%d%d",&a,&b);
46         printf("Case %d: %d
",++icase,solve(b)-solve(a-1));
47     }
48     return 0;
49 }