fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3.  
  4. #define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cin.tie(nullptr);
  5. // #define int long long
  6. #define ld long double
  7. #define pb emplace_back
  8. #define range(v) v.begin(),v.end()
  9. #define mod (int)(1e9 + 7)
  10. #define inf (int)(1e15)
  11. #define pii pair<int,int>
  12. #define ff first
  13. #define ss second
  14. #define endl '\n'
  15. //#define N (int)()
  16.  
  17. using namespace std;
  18.  
  19. int dp[50][2][17][17][17];
  20. char l[50], r[50];
  21. int n;
  22.  
  23. int tsn(char *s, int i = 0, bool tight = true, int tc = 0, int sc = 0, int nc = 0) {
  24.     int ans = 0;
  25.     int lim = tight ? s[i] - '0' : 9;
  26.  
  27.     if (i == n)
  28.         return tc and tc == sc and sc == nc;
  29.     if (tc > (n / 3) or sc > (n / 3) or nc > (n / 3))
  30.         return 0;
  31.     if (dp[i][tight][tc][sc][nc] != -1)
  32.         return dp[i][tight][tc][sc][nc];
  33.  
  34.     for (int j = 0; j <= lim; j++)
  35.         ans += tsn(s, i + 1, tight and (j == lim), tc + (j == 3), sc + (j == 6), nc + (j == 9)) % mod, ans %= mod;
  36.  
  37.     return dp[i][tight][tc][sc][nc] = ans;
  38. }
  39.  
  40. bool isNo(char *s) {
  41.     int v[10] = {};
  42.     for (int i = 0; s[i] != '\0'; i++) {
  43.         char c = s[i];
  44.         v[c - '0']++;
  45.     }
  46.     return v[3] and (v[3] == v[6] and v[6] == v[9]);
  47. }
  48.  
  49. int32_t main() {
  50.     fast
  51.     int t_c = 1;
  52.     cin >> t_c;
  53.     while (t_c--) {
  54.         scanf("%s %s", l, r);
  55.         memset(dp, -1, sizeof(dp));
  56.         n = strlen(l);
  57.         int a = tsn(l) % mod;
  58.         memset(dp, -1, sizeof(dp));
  59.         n = strlen(r);
  60.         int b = tsn(r) % mod;
  61.         cout << ((b - a + mod) % mod) + isNo(l) << endl;
  62.     }
  63. }
  64.  
Success #stdin #stdout 0s 5736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/dR8nUV
language:
C++14 (gcc 8.3)
created:
5 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!