fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define mod 1000000007
  3.  
  4. using namespace std;
  5.  
  6. typedef long long int ll;
  7.  
  8. ll dp[51][33][33][2][2], a[51], n;
  9.  
  10. ll foo(int pos, int six_minus_three, int nine_minus_six, int flag, int if_any_3){
  11.     int mapped_six = (six_minus_three < 0)? 16 - six_minus_three : six_minus_three;
  12.     int mapped_nine = (nine_minus_six < 0)? 16 - nine_minus_six : nine_minus_six;
  13.  
  14.     if(six_minus_three >= 17 || nine_minus_six >= 17 || nine_minus_six <= -17 || six_minus_three <= -17) return 0;
  15.     if(pos >= n) return ((six_minus_three == 0) & (nine_minus_six == 0) & if_any_3);
  16.     if(dp[pos][mapped_six][mapped_nine][flag][if_any_3] != -1) return dp[pos][mapped_six][mapped_nine][flag][if_any_3];
  17.  
  18.     ll ans = 0;
  19.     int last = (flag == 1)? a[pos] : 9;
  20.     for(int j = 0; j <= last; j++){
  21.         if(j == 3) ans += foo(pos+1, six_minus_three - 1, nine_minus_six, (flag && j == last)? flag : 0, 1);
  22.         else if(j == 6) ans += foo(pos+1, six_minus_three + 1, nine_minus_six - 1, (flag && j == last)? flag : 0, if_any_3);
  23.         else if(j == 9) ans += foo(pos+1, six_minus_three, nine_minus_six + 1, (flag && j == last)? flag : 0, if_any_3);
  24.         else ans += foo(pos+1, six_minus_three, nine_minus_six, (flag && j == last)? flag : 0, if_any_3);
  25.         ans %= mod;
  26.     }
  27.     dp[pos][mapped_six][mapped_nine][flag][if_any_3] = ans;
  28.     return ans;
  29. }
  30.  
  31. int main(){
  32.     ios_base :: sync_with_stdio(false);
  33.     cin.tie(NULL);
  34.  
  35.     int t;
  36.     cin >> t;
  37.     while(t--){
  38.         string s1, s2;
  39.         cin >> s1 >> s2;
  40.  
  41.         memset(dp, -1, sizeof(dp));
  42.         n = s1.length();
  43.         for(int j = 0; j < n; j++)
  44.             a[j] = s1[j] - '0';
  45.         ll ans1 = foo(0, 0, 0, 1, 0);
  46.  
  47.         memset(dp, -1, sizeof(dp));
  48.         n = s2.length();
  49.         for(int j = 0; j < n; j++)
  50.             a[j] = s2[j] - '0';
  51.         ll ans2 = foo(0, 0, 0, 1, 0);
  52.  
  53.         cout << (ans2 - ans1 + mod) % mod << endl;
  54.     }
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0s 17800KB
comments (?)
stdin
copy 
2
1 100000000000000000000000000000000000000000000000000
1 100000000000000000000000000000000000000000000000000
stdout
copy 
129112453
129112453
https://ideone.com/PAVdOT
language:
C++14 (gcc 8.3)
created:
6 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!