fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef loc
  5.     #include "loc_debug.h"
  6. #else
  7.     #define pr(...)
  8.     #define pra(a,n)
  9.     #define praa(a,n,m)
  10.     #define prl()
  11. #endif
  12.  
  13. typedef long long ll;
  14. typedef long double ld;
  15. #define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  16. #define mp make_pair
  17. #define pb push_back
  18. #define eb emplace_back
  19. #define all(x) (x).begin(), (x).end()
  20. #define sz(a) int(a.size())
  21. #define rep(i, s, n)  for(int i = s; i <= n; ++i)
  22. #define rev(i, n, s)  for(int i = n; i >= s; --i)
  23. #define fore(x, a) for(auto &&x : a)
  24. #define fill(a, x) memset((a), (x), sizeof(a))
  25. #define tcase int __t; cin >> __t; rep(tc, 1, __t)
  26. #define F first
  27. #define S second
  28. #define gc getchar
  29.  
  30. const int mod = 1000000007;
  31. #define _ %mod
  32. const int N = 100005;
  33.  
  34. int dp[55][17][17][17];
  35. int a[55];
  36.  
  37. bool is369(string s) {
  38.     map<char, int> b;
  39.     fore(x, s) {
  40.         b[x]++;
  41.     }
  42.     if(b['3'] == b['6'] && b['6'] == b['9'] && b['3']) {
  43.         return true;
  44.     }
  45.     return false;
  46. }
  47.  
  48. int f(int p, int c3, int c6, int c9) {
  49.     if(p == -1) {
  50.         return c3 == 0 && c6 == 0 && c9 == 0;
  51.     }
  52.     if(c3 >= 0 && c6 >= 0 && c9 >= 0 && c3 < 17 && c6 < 17 && c9 < 17) {
  53.         return dp[p][c3][c6][c9];
  54.     }
  55.     return 0;
  56. }
  57.  
  58. int count(string s) {
  59.     fill(a, 0);
  60.     reverse(all(s));
  61.     rep(i, 0, sz(s) - 1) {
  62.         a[i] = s[i] - '0';
  63.     }
  64.     int res = 0;
  65.     pra(a, 10);
  66.     rep(c, 1, 16) {
  67.         int c3 = 0, c6 = 0, c9 = 0;
  68.         rev(i, 50, 0) {
  69.             rep(j, 0, a[i] - 1) {
  70.                 if(j == 3) {
  71.                     c3++;
  72.                 }
  73.                 if(j == 6) {
  74.                     c6++;
  75.                 }
  76.                 if(j == 9) {
  77.                     c9++;
  78.                 }
  79.                 res += f(i - 1, c - c3, c - c6, c - c9);
  80.                 if(res >= mod) {
  81.                     res -= mod;
  82.                 }
  83.                 if(j == 3) {
  84.                     c3--;
  85.                 }
  86.                 if(j == 6) {
  87.                     c6--;
  88.                 }
  89.                 if(j == 9) {
  90.                     c9--;
  91.                 }
  92.             }
  93.             if(a[i] == 3) {
  94.                 c3++;
  95.             }
  96.             if(a[i] == 6) {
  97.                 c6++;
  98.             }
  99.             if(a[i] == 9) {
  100.                 c9++;
  101.             }
  102.         }
  103.     }
  104.     return res;
  105. }
  106.  
  107. int main() {
  108.     fast_io;
  109.     dp[0][0][0][0] = 7;
  110.     dp[0][1][0][0] = 1;
  111.     dp[0][0][1][0] = 1;
  112.     dp[0][0][0][1] = 1;
  113.     rep(p, 1, 49) {
  114.         rep(c3, 0, 16) {
  115.             rep(c6, 0, 16) {
  116.                 rep(c9, 0, 16) {
  117.                     rep(i, 0, 9) {
  118.                         int b3 = c3, b6 = c6, b9 = c9;
  119.                         if(i == 3) {
  120.                             b3--;
  121.                         }
  122.                         if(i == 6) {
  123.                             b6--;
  124.                         }
  125.                         if(i == 9) {
  126.                             b9--;
  127.                         }
  128.                         if(b3 >= 0 && b6 >= 0 && b9 >= 0) {
  129.                             dp[p][c3][c6][c9] += dp[p - 1][b3][b6][b9];
  130.                             if(dp[p][c3][c6][c9] >= mod) {
  131.                                 dp[p][c3][c6][c9] -= mod;
  132.                             }
  133.                         }
  134.                     }
  135.                 }
  136.             }
  137.         }
  138.     }
  139.     tcase {
  140.         string s1(55, '0'), s2(55, '0');
  141.         cin >> s1 >> s2;
  142.         int res = count(s2) - count(s1);
  143.         if(res < 0) {
  144.             res += mod;
  145.         }
  146.         if(is369(s2)) {
  147.             res++;
  148.             if(res >= mod) {
  149.                 res -= mod;
  150.             }
  151.         }
  152.         cout << res << endl;
  153.     }
  154.     return 0;
  155. }
  156.  
Success #stdin #stdout 0.02s 4432KB
comments (?)
stdin
copy 
3

121 4325

432 4356

4234 4325667
stdout
copy 
60
58
207159
https://ideone.com/27hw2y
language:
C++14 (gcc 8.3)
created:
6 years 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!