fork download 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. typedef int ll;
  4. using namespace std;
  5.  
  6. const ll MOD = 1e9 + 7;
  7. ll dp[51][17][17][17][2], t;
  8. unordered_map<string, ll> cnt;
  9. string a, b;
  10.  
  11. ll f(string &s, ll pos, ll three, ll six, ll nine, ll tight) {
  12.     if (three > s.size() / 3 || six > s.size() / 3 || nine > s.size() / 3) return 0;
  13.     if (pos == 0) {
  14.         if ((three == six) && (six == nine) && three > 0) return 1;
  15.         return 0;
  16.     }
  17.     ll res = dp[pos][three][six][nine][tight];
  18.     if (res != -1) return res;
  19.     ll ans = 0, limit = (tight == 1) ? (s[s.size() - pos] - '0') : 9;
  20.     for (ll i = 0; i <= limit; i++) {
  21.         if (i == 3) {
  22.             ans += f(s, pos - 1, three + 1, six, nine, (tight & (limit == i)));
  23.         } else if (i == 6) {
  24.             ans += f(s, pos - 1, three, six + 1, nine, (tight & (limit == i)));
  25.         } else if (i == 9) {
  26.             ans += f(s, pos - 1, three, six, nine + 1, (tight & (limit == i)));
  27.         } else {
  28.             ans += f(s, pos - 1, three, six, nine, (tight & (limit == i)));
  29.         }
  30.         ans %= MOD;
  31.     }
  32.     dp[pos][three][six][nine][tight] = ans % MOD;
  33.     return ans % MOD;
  34. }
  35.  
  36. ll g(string &s) {
  37.     ll three = 0, six = 0, nine = 0;
  38.     for (ll i = 0; i < s.size(); i++) {
  39.         if (s[i] == '3') three++;
  40.         if (s[i] == '6') six++;
  41.         if (s[i] == '9') nine++;
  42.     }
  43.     return ((three == six) && (six == nine) && three > 0);
  44. }
  45.  
  46. void sol() {
  47.     cin >> a >> b;
  48.     memset(dp, -1, sizeof(dp));
  49.     ll ans = f(b, b.size(), 0, 0, 0, 1);
  50.     memset(dp, -1, sizeof(dp));
  51.     ll val = ans - f(a, a.size(), 0, 0, 0, 1) + g(a);
  52.     if (val >= MOD) val -= MOD;
  53.     else if (val < 0) val += MOD;
  54.     cout << val << endl;
  55. }
  56.  
  57. int main() {
  58.     ios::sync_with_stdio(0);
  59.     cin.tie(0);
  60.  
  61. //    freopen(".INP", "r", stdin);
  62. //    freopen(".OUT", "w", stdout);
  63.  
  64.     cin >> t;
  65.     while (t--) sol();
  66.  
  67.     return 0;
  68. }
  69.  
  70.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Lmx2jr
language:
C++14 (gcc 8.3)
created:
2 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!