LightOJ1068 Investigation（数位DP）

这题要求区间有多少个模K且各位数之和模K都等于0的数字。

注意到[1,2³¹]这些数最大的各位数之和不会超过90左右，而如果K大于90那么模K的结果肯定不是0，因此K大于90就没有解。

考虑到数据规模，数据组数，这题状态这么表示：

dp[i][j][k]：位数为i模K结果为j且各位数之和模K结果为k的数字个数

然后就是转移方程，最后就是统计。。

统计部分好棘手。。。半乱搞下AC的。。还是对数位DP的这一部分太不熟悉了。

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int K,d[11][90][90],pow[10]={1};
 5 int calu(int n){
 6     int res=0,pre=0,sum=0;
 7     for(int i=9; i>=0; --i){
 8         if(i==0) for(int j=0; j<=n/pow[i]%10; ++j) res+=d[i][(K-((pre*10+j)*pow[i])%K)%K][(K-(sum+j)%K)%K];
 9         else for(int j=0; j<n/pow[i]%10; ++j) res+=d[i][(K-((pre*10+j)*pow[i])%K)%K][(K-(sum+j)%K)%K];
10         pre=pre*10+n/pow[i]%10;
11         sum+=n/pow[i]%10;
12     }
13     return res;
14 }
15 int main(){
16     for(int i=1; i<10; ++i) pow[i]=pow[i-1]*10;
17     int t,a,b;
18     scanf("%d",&t);
19     for(int cse=1; cse<=t; ++cse){
20         scanf("%d%d%d",&a,&b,&K);
21         if(K>=90){
22             printf("Case %d: %d
",cse,0);
23             continue; 
24         }
25         memset(d,0,sizeof(d));
26         d[0][0][0]=1;
27         for(int i=0; i<10; ++i) ++d[1][i%K][i%K];
28         for(int len=1; len<10; ++len){
29             for(int i=0; i<K; ++i){
30                 for(int j=0; j<K; ++j){
31                     if(d[len][i][j]==0) continue;
32                     for(int k=0; k<10; ++k) d[len+1][(i*10+k)%K][(j+k)%K]+=d[len][i][j];
33                 }
34             }
35         }
36         printf("Case %d: %d
",cse,calu(b)-calu(a-1));
37     }
38     return 0;
39 }