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. int dp[52][18][18][18][2];
  12. int vis[52][18][18][18][2];
  13. int testCase = 1;
  14. string subtractOne(string s) {
  15.     if (s == "0") return "0";
  16.     int n = s.size();
  17.     for (int i = n - 1; i >= 0; i--) {
  18.         if (s[i] > '0') {
  19.             s[i]--;
  20.             break;
  21.         } else s[i] = '9';
  22.     }
  23.     int first = s.find_first_not_of('0');
  24.     return (first == string::npos) ? "0" : s.substr(first);
  25. }
  26. void sol() {
  27.   string l , r;
  28.   cin >> l >> r;
  29.   string s = r;
  30.   function<int(int,int,int,int,bool)>recur = [&](int idx , int cnt3 , int cnt6 , int cnt9 , bool tight) -> int {
  31.     if(cnt3 >= 18 || cnt6 >= 18 || cnt9 >= 18)
  32.       return 0;
  33.     if(idx == s.size())
  34.       return (cnt3 > 0 && cnt3 == cnt6 && cnt6 == cnt9);
  35.     int &ret = dp[idx][cnt3][cnt6][cnt9][tight];
  36.     if(vis[idx][cnt3][cnt6][cnt9][tight] == testCase) 
  37.       return ret;
  38.     vis[idx][cnt3][cnt6][cnt9][tight] = testCase;
  39.     ret = 0;
  40.     int end = (tight ? s[idx] - '0' : 9);
  41.     for (int i = 0; i <= end; ++i) {
  42.         ret = (ret + recur(idx + 1, cnt3 + (i == 3), cnt6 + (i == 6), cnt9 + (i == 9), tight && (i == end))) % Mod;
  43.     }
  44.     return ret;
  45.   };
  46.   s = r;
  47.   testCase++;
  48.   int ansB = recur(0, 0, 0, 0, 1);
  49.   s = subtractOne(l);
  50.   testCase++;
  51.   int ansA = recur(0, 0, 0, 0, 1);
  52.   cout << (ansB - ansA + Mod) % Mod << '\n';
  53. }
  54. int32_t main()
  55. {
  56.   Fast;
  57.   int t = 1;
  58.   cin >> t;
  59.   while(t--) {
  60.     sol();
  61.   }
  62. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ILmQiv
language:
C++14 (clang 8.0)
created:
3 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!