Lightoj 1140 How Many zeros

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

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int NX = 70 ;
4.  
5. long long int dp[2][2][NX][NX];
6. long long int vis[2][2][NX][NX];
7. long long int lim , tt ;
8. vector < int > inp ;
9.  
10. long long int DP( int pos , int isSmall ,int isStart, int value)
11. {
12.     if( pos == lim ) return value ;
13.     long long int &ret = dp[isSmall][isStart][pos][value];
14.     long long int &v = vis[isSmall][isStart][pos][value];
15.     if( v == tt ) return ret ;
16.     v = tt ;
17.     int ses = isSmall ? 9 : inp[pos];
18.     int i ;
19.     ret = 0 ;
20.     if( !isStart ) 
21.     for ( i = 0 ; i <= ses ; i++ )
22.     {
23.         ret += DP( pos + 1 , isSmall | i < inp[pos] ,0, (i == 0) + value );
24.     }
25.     else
26.     {
27.          for ( i = 1 ; i <= ses ; i++ )
28.     {
29.         ret += DP( pos + 1 , isSmall | i < inp[pos] ,0, (i == 0) + value );
30.     }
31.     ret += DP( pos + 1 , 1 ,1, 0 );
32.     }
33.     return ret ;
34. }
35.  
36. long long int Cal(long long int x )
37. {
38.     if( x < 0 ) return 0 ;
39.     if( x <= 9 ) return 1 ;
40.     inp.clear();
41.     while( x )
42.     {
43.         inp.push_back(x%10);
44.         x/=10;
45.     }
46.     reverse(inp.begin(),inp.end()); 
47.     lim = inp.size();
48.     tt++;
49.     return DP( 0 , 0 , 1 , 0 ) + 1;
50. }
51. int main()
52. {
53.      int cs , t;
54.      cin>>t;
55.      for ( cs = 1 ; cs <= t ; cs++ )
56.      {
57.  
58.         long long int n , m;
59.         cin>>n>>m;
60.         long long int ans = Cal(m) - Cal(n-1);
61.         printf("Case %d: %lld\n",cs,ans);
62.      }
63.     return 0;
64. }