fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define initial first
  8. #define added second
  9. #define sort_all(v) sort(v.begin(), v.end())
  10.  
  11. #define ya_sayed_ya_badawy            \
  12.     ios_base::sync_with_stdio(false); \
  13.     cin.tie(NULL);
  14.  
  15. const int MAX = 50 + 5;
  16. int MOD = 1000000007;
  17. const int OO = 1e9;
  18. const double EPS = (double)1e-9;
  19.  
  20. string a, b;
  21. int mem[MAX][2][2][2][50][50];
  22. int visited[MAX][2][2][2][50][50];
  23.  
  24. const int offset = 17;
  25.  
  26. int id = 1;
  27.  
  28. int add(ll a, ll b)
  29. {
  30.     return ((a % MOD) + (b % MOD)) % MOD;
  31. }
  32.  
  33. int mul(ll a, ll b)
  34. {
  35.     return ((a % MOD) * (b % MOD)) % MOD;
  36. }
  37.  
  38. int fp(int base, int pow)
  39. {
  40.     if (pow == 0)
  41.     {
  42.         return 1;
  43.     }
  44.  
  45.     int res = fp(base, pow / 2);
  46.  
  47.     if (pow % 2 == 0)
  48.     {
  49.         return mul(res, res);
  50.     }
  51.     return mul(base, mul(res, res));
  52. }
  53.  
  54. int dp(int pos, bool exceeded_lower, bool below_upper, bool three, int diff1, int diff2)
  55. {
  56.     if (pos == (int)b.size())
  57.     {
  58.         return (diff1 == offset) && (diff2 == offset) && (three);
  59.     }
  60.  
  61.     int &ret = mem[pos][exceeded_lower][below_upper][three][diff1][diff2];
  62.     if (visited[pos][exceeded_lower][below_upper][three][diff1][diff2] == id)
  63.     {
  64.         return ret;
  65.     }
  66.  
  67.     visited[pos][exceeded_lower][below_upper][three][diff1][diff2] = id;
  68.  
  69.     ret = 0;
  70.     int low = exceeded_lower ? 0 : (a[pos] - '0');
  71.     int high = below_upper ? 9 : (b[pos] - '0');
  72.  
  73.     for (int d = low; d <= high; ++d)
  74.     {
  75.         bool new_tight_low = exceeded_lower || (d > (a[pos] - '0'));
  76.         bool new_tight_high = below_upper || (d < (b[pos] - '0'));
  77.         bool new_three = three || (d == 3);
  78.  
  79.         int new_diff1 = diff1, new_diff2 = diff2;
  80.  
  81.         if (d == 3)
  82.         {
  83.             new_diff1 -= 1;
  84.         }
  85.         if (d == 6)
  86.         {
  87.             new_diff1 += 1;
  88.             new_diff2 -= 1;
  89.         }
  90.         if (d == 9)
  91.         {
  92.             new_diff2 += 1;
  93.         }
  94.  
  95.         ret = add(ret, dp(pos + 1, new_tight_low, new_tight_high, new_three, new_diff1, new_diff2));
  96.     }
  97.  
  98.     return ret;
  99. }
  100.  
  101. string normalize_length(string s, int len)
  102. {
  103.     return (string(len - (int)s.size(), '0') + s);
  104. }
  105.  
  106. void solve(int t)
  107. {
  108.     cin >> a >> b;
  109.  
  110.     int max_len = max(a.size(), b.size());
  111.     a = normalize_length(a, max_len);
  112.     b = normalize_length(b, max_len);
  113.  
  114.     int result = dp(0, 0, 0, 0, offset, offset);
  115.  
  116.     id++;
  117.  
  118.     cout << result;
  119. }
  120.  
  121. signed main()
  122. {
  123.     ya_sayed_ya_badawy int t = 1;
  124.     cin >> t;
  125.  
  126.     for (int i = 1; i <= t; i++)
  127.     {
  128.         solve(i);
  129.         cout << "\n";
  130.     }
  131.  
  132.     return 0;
  133. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/xbhBQx
language:
C++14 (gcc 8.3)
created:
5 days 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!