fork download
copy 
  1. #include<bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. #define MOD 1000000007
  5. int TC;
  6. char s[55];
  7. char A[55] , B[55];
  8. int len;
  9. ll memo[51][18][18][18][2];
  10.  
  11. ll solve(int idx, int three, int six, int nine, bool isGreater) {
  12.     int mx = max( three , max( six , nine ) );
  13.     if( mx > 16 )
  14.         return 0;
  15.     if (idx == len)
  16.         return ( (three == six) && (six == nine) && (three != 0) && (!isGreater));
  17.  
  18.     if ( ~memo[idx][three][six][nine][isGreater])
  19.         return memo[idx][three][six][nine][isGreater];
  20.  
  21.     int cur = s[idx] - '0';
  22.     ll res = 0;
  23.     if (isGreater) {
  24.         for (int i = 0; i <= 9; i++) {
  25.             res += solve(idx + 1, three + (i == 3), six + (i == 6), nine + (i == 9), i >= cur);
  26.             res %= MOD;
  27.         }
  28.     } else {
  29.         for (int i = 0; i <= 9; i++) {
  30.             res += solve(idx + 1, three + (i == 3), six + (i == 6), nine + (i == 9), i > cur);
  31.             res %= MOD;
  32.         }
  33.     }
  34.     return memo[idx][three][six][nine][isGreater] = res;
  35. }
  36.  
  37. bool check(){
  38.     int three = 0 , six = 0 , nine = 0;
  39.     for(int i=0;i<len;i++){
  40.         three += ( s[i] == '3' );
  41.         six += ( s[i] == '6' );
  42.         nine += ( s[i] == '9' );
  43.     }
  44.     return ( ( three == six ) && ( six == nine ) && ( three != 0 ) );
  45. }
  46.  
  47. int main() {
  48. #ifndef ONLINE_JUDGE
  49.     freopen("in.in", "r", stdin);
  50.     freopen("out.out", "w", stdout);
  51.     double startTime = clock();
  52. #endif
  53.  
  54.     scanf("%d", &TC);
  55.     while (TC--) {
  56.         scanf("%s %s" , &A , &B );
  57.         //
  58.         len = strlen( B );
  59.         for(int i=len-1;i>=0;i--)
  60.             s[len - 1 - i] = B[i];
  61.         memset(memo , -1 , sizeof memo);
  62.         ll right = solve( 0 , 0 , 0 , 0 , 0 ) % MOD;
  63.         //
  64.         len = strlen( A );
  65.         for(int i=len-1;i>=0;i--)
  66.             s[len - 1 - i] = A[i];
  67.         memset(memo , -1 , sizeof memo);
  68.         ll left = solve( 0 , 0 , 0 , 0 , 0 ) % MOD;
  69.         //
  70.         ll res = right - left;
  71.         res += check();
  72.         res = ( res + MOD + MOD ) % MOD;
  73.         printf("%lld\n" , res );
  74.         //
  75.     }
  76.  
  77. #ifndef ONLINE_JUDGE
  78.     cout << "Runtime is : " << (clock() - startTime) / CLOCKS_PER_SEC << '\n';
  79. #endif
  80. }
Success #stdin #stdout 0.01s 8104KB
comments (?)
stdin
copy 
3
121 4325
432 4356
4234 4325667
stdout
copy 
60
58
207159
https://ideone.com/MM0D2G
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!