Lightoj 1068 Investigation

http://lightoj.com/volume_showproblem.php?problem=1068

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define  ll long long int
4.  
5. ll  DP[2][11][82][82];
6. int lim, tt, k;
7. vector<int>inp;
8. ll dp(int pos,int issmall,int digrem,int numrem){
9.         if(pos == lim){
10.             return !(digrem+numrem);
11.         }
12.         if(DP[issmall][pos][digrem][numrem]!= -1){
13.             return DP[issmall][pos][digrem][numrem];
14.         }
15.         ll ret = 0;
16.         int mx = (issmall)? 9:inp[pos];
17.         for(int i = 0; i <mx; i++){
18.             ret+= dp(pos+1, 1, (digrem+i)%k, (numrem*10+i)%k);
19.         }
20.         ret+= dp(pos+1, issmall,(digrem+mx)%k, (numrem*10+mx)%k);
21.         DP[issmall][pos][digrem][numrem] = ret;
22.         return ret;
23. }
24.  
25. int solve (int n){
26.     inp.clear();
27.     int sum= 0;
28.     while(n!= 0){
29.             sum+= n%10;
30.         inp.push_back(n%10);
31.         n = n/10;
32.     }
33.     reverse(inp.begin(), inp.end());
34.     lim = inp.size();
35.     tt++;
36.     return dp(0, 0, 0, 0);
37. }
38. int main()
39. {
40.     ll a, b;
41.     int ts;
42.     cin>>ts;
43.     for(int i   = 1; i <=ts; i++){
44.     cin>>a>>b>>k;
45.     ll ans;
46.     if(k >= 82 ){
47.         cout<<"Case "<<i<<": "<<"0"<<endl;
48.     }
49.     else if(k == 1){
50.         cout<<"Case "<<i<<": "<<b-a+1<<endl;
51.     }
52.     else{
53.     memset(DP, -1, sizeof(DP));
54.     ans = solve(b);
55.     memset(DP, -1, sizeof(DP));
56.     ans-= solve(a-1);
57.     cout<<"Case "<<i<<": "<<ans<<endl;
58.     }
59.     }
60.     return 0;
61. }