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 + b) % MOD;
  31. }
  32.  
  33. int mul(ll a, ll b)
  34. {
  35.     return (a * b) % MOD;
  36. }
  37.  
  38. int dp(int pos, bool exceeded_lower, bool below_upper, bool three, int diff1, int diff2)
  39. {
  40.  
  41.     if (pos == (int)b.size())
  42.     {
  43.         return (diff1 == offset) && (diff2 == offset) && (three);
  44.     }
  45.  
  46.     int remaining = (int)b.size() - pos;
  47.     int mxToBalance = max(abs(diff1 - offset), abs(diff2 - offset));
  48.     if (mxToBalance > remaining)
  49.     {
  50.         return 0;
  51.     }
  52.  
  53.     int &ret = mem[pos][exceeded_lower][below_upper][three][diff1][diff2];
  54.     if (visited[pos][exceeded_lower][below_upper][three][diff1][diff2] == id)
  55.     {
  56.         return ret;
  57.     }
  58.  
  59.     visited[pos][exceeded_lower][below_upper][three][diff1][diff2] = id;
  60.  
  61.     ret = 0;
  62.     int low = exceeded_lower ? 0 : (a[pos] - '0');
  63.     int high = below_upper ? 9 : (b[pos] - '0');
  64.  
  65.     for (int d = low; d <= high; ++d)
  66.     {
  67.         bool new_tight_low = exceeded_lower || (d > (a[pos] - '0'));
  68.         bool new_tight_high = below_upper || (d < (b[pos] - '0'));
  69.         bool new_three = three || (d == 3);
  70.  
  71.         int new_diff1 = diff1, new_diff2 = diff2;
  72.  
  73.         if (d == 3)
  74.         {
  75.             new_diff1 -= 1;
  76.         }
  77.         if (d == 6)
  78.         {
  79.             new_diff1 += 1;
  80.             new_diff2 -= 1;
  81.         }
  82.         if (d == 9)
  83.         {
  84.             new_diff2 += 1;
  85.         }
  86.  
  87.         ret = add(ret, dp(pos + 1, new_tight_low, new_tight_high, new_three, new_diff1, new_diff2));
  88.     }
  89.  
  90.     return ret;
  91. }
  92.  
  93. string normalize_length(string s, int len)
  94. {
  95.     return (string(len - (int)s.size(), '0') + s);
  96. }
  97.  
  98. void solve(int t)
  99. {
  100.     cin >> a >> b;
  101.  
  102.     int max_len = max(a.size(), b.size());
  103.     a = normalize_length(a, max_len);
  104.     b = normalize_length(b, max_len);
  105.  
  106.     int result = dp(0, 0, 0, 0, offset, offset);
  107.  
  108.     id++;
  109.  
  110.     cout << result;
  111. }
  112.  
  113. signed main()
  114. {
  115.     ya_sayed_ya_badawy int t = 1;
  116.     cin >> t;
  117.  
  118.     for (int i = 1; i <= t; i++)
  119.     {
  120.         solve(i);
  121.         if (i != t)
  122.         {
  123.             cout << "\n";
  124.         }
  125.     }
  126.  
  127.     return 0;
  128. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uyo64d
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!