fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Fast                      \
  4.   {                               \
  5.     ios_base::sync_with_stdio(0); \
  6.     cin.tie(0);                   \
  7.     cout.tie(0);                  \
  8.   }
  9. #define int long long
  10. const int MOD = 1e9 + 7;
  11. const int Limit = 55;
  12. int dp[55][110][110][2][2][2];
  13. void sol()
  14. {
  15.   string A, B;
  16.   cin >> A >> B;
  17.   string s;
  18.   function<int(int, int, int, int, int, int)> recur = [&](int idx, int d1, int d2, int tight, int started, int has3) -> int
  19.   {
  20.     if (idx == (int)s.size())
  21.       return (d1 == Limit && d2 == Limit && has3);
  22.     int &ret = dp[idx][d1][d2][tight][started][has3];
  23.     if (ret != -1)
  24.       return ret;
  25.     ret = 0;
  26.     int end = (tight ? s[idx] - '0' : 9);
  27.     for (int i = 0; i <= end; i++)
  28.     {
  29.       int ns = (started || (i != 0));
  30.       int nd1 = d1 + (ns && i == 3) - (ns && i == 6);
  31.       int nd2 = d2 + (ns && i == 6) - (ns && i == 9);
  32.       if (nd1 < 0 || nd1 >= 110 || nd2 < 0 || nd2 >= 110)
  33.         continue;
  34.       ret = (ret + recur(idx + 1, nd1, nd2, (tight && (i == end)), ns, (has3 || (ns && i == 3)))) % MOD;
  35.     }
  36.     return ret;
  37.   };
  38.   auto minusOne = [&](string a)
  39.   {
  40.     int i = a.size() - 1;
  41.     while (i >= 0 && a[i] == '0')
  42.     {
  43.       a[i] = '9';
  44.       i--;
  45.     }
  46.     if (i >= 0)
  47.       a[i]--;
  48.     if (a[0] == '0')
  49.     {
  50.       int j = 0;
  51.       while (j < (int)a.size() && a[j] == '0')
  52.         j++;
  53.       if (j == (int)a.size())
  54.         return string("0");
  55.       a = a.substr(j);
  56.     }
  57.     return a;
  58.   };
  59.   s = B;
  60.   memset(dp, -1, sizeof(dp));
  61.   int resB = recur(0, Limit, Limit, 1, 0, 0);
  62.   A = minusOne(A);
  63.   s = A;
  64.   memset(dp, -1, sizeof(dp));
  65.   int resA = recur(0, Limit, Limit, 1, 0, 0);
  66.   int ans = (resB - resA) % MOD;
  67.   if (ans < 0)
  68.     ans += MOD;
  69.   cout << ans << '\n';
  70. }
  71. int32_t main()
  72. {
  73.   Fast;
  74.   int t = 1;
  75.   cin >> t;
  76.   while (t--)
  77.   {
  78.     sol();
  79.   }
  80. }
Success #stdin #stdout 0.02s 45268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/MXk58i
language:
C++14 (clang 8.0)
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!