Lightoj1068——Investigation（数位dp）-白红宇

Lightoj1068——Investigation（数位dp）

阅读量：2345 次

发布时间：2019-05-10

本文共 1711 字，大约阅读时间需要 5 分钟。

An integer is divisible by 3 if the sum of its digits is also divisible by 3. For example, 3702 is divisible by 3 and 12 (3+7+0+2) is also divisible by 3. This property also holds for the integer 9.

In this problem, we will investigate this property for other integers.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains three positive integers A, B and K (1 ≤ A ≤ B < 231 and 0 < K < 10000).

Output

For each case, output the case number and the number of integers in the range [A, B] which are divisible by K and the sum of its digits is also divisible by K.

Sample Input

1 20 1

1 20 2

1 1000 4

Output for Sample Input

Case 1: 20

Case 2: 5

Case 3: 64

两个参数，一个表示每位数之和，另一表示该数除以k的结果

WA了几次，发现数组开小了

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define MAXN 10000005#define Mod 10001using namespace std;int dight[40];long long dp[40][100][100],k;long long dfs(int pos,int s,bool limit,int mod){ if(pos==0) return mod==0&&(s%k==0)&&s>=1; if(!limit&&dp[pos][s][mod]!=-1) return dp[pos][s][mod]; int end; long long ret=0; if(limit) end=dight[pos]; else end=9; for(int d=0; d<=end; ++d) { int ss=s+d; int nmod=(mod*10+d)%k; ret+=dfs(pos-1,ss,limit&&d==end,nmod); } if(!limit) dp[pos][s][mod]=ret; return ret;}long long solve(long long a){ memset(dight,0,sizeof(dight)); int cnt=1; while(a!=0) { dight[cnt++]=a%10; a/=10; } return dfs(cnt-1,0,1,0);}int main(){ int t,cnt=1; scanf("%d",&t); while(t--) { memset(dp,-1,sizeof(dp)); long long x,y; scanf("%lld%lld%lld",&x,&y,&k); printf("Case %d: %lld\n",cnt++,solve(y)-solve(x-1)); } return 0;}

转载地址：http://cvcvb.baihongyu.com/

你可能感兴趣的文章