fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(1e4)+7;
  14. const int mod = int(1e9)+7;
  15.  
  16. int add(int x , int y){
  17.     x += y;
  18.     if (x >= mod) x -= mod;
  19.     return x;
  20. }
  21.  
  22. void self_add(int &x , int y){
  23.     x = add(x , y);
  24. }
  25.  
  26. int sub(int x , int y){
  27.     x -= y;
  28.     if (x < 0) x += mod;
  29.     return x;
  30. }
  31.  
  32. void self_sub(int &x , int y){
  33.     x = sub(x , y);
  34. }
  35.  
  36. int p[maxN] , dp[maxN][2][2][9][20];
  37.  
  38. int calc(string &s , int id , int zero , int tight , int mask , int modu){
  39.     if (id == -1) return (modu == 0);
  40.     int &ans = dp[id][zero][tight][mask][modu];
  41.     if (tight == 1 && ans != -1) return ans;
  42.     ans = 0;
  43.     for (int c = 0 ; c < 10 ; c++){
  44.         if (tight == 0 && c > (s[id] - '0')) continue;
  45.         int x = (3 - c % 3) % 3;
  46.         int y = c % 3;
  47.         if ((mask>>x)&1) continue;
  48.         int nxt_zero = (zero | (c != 0));
  49.         int nxt_tight = (tight | (c < (s[id] - '0')));
  50.         int nxt_mask = mask;
  51.         if (c != 0 || (c == 0 && zero == 1)){
  52.             nxt_mask |= (1<<y);
  53.         }
  54.         int nxt_modu = (modu + c * p[id]) % 19;
  55.         self_add(ans , calc(s , id - 1 , nxt_zero , nxt_tight , nxt_mask , nxt_modu));
  56.     }
  57.     return ans;
  58. }
  59.  
  60. int calc(string &s){
  61.     reverse(all(s));
  62.     return calc(s , sz(s) - 1 , 0 , 0 , 0 , 0);
  63. }
  64.  
  65. bool check(string &s){
  66.     int mask = 0;
  67.     int modu = 0;
  68.     for (int i = sz(s) - 1 ; i >= 0 ; i--){
  69.         char c = s[i];
  70.         int x = (3 - (c - '0') % 3) % 3;
  71.         int y = (c - '0') % 3;
  72.         if ((mask>>x)&1) return 0;
  73.         mask |= (1<<y);
  74.         modu = (modu + (s[i] - '0') * p[i]) % 19;
  75.     }
  76.     return (modu == 0);
  77. }
  78.  
  79. void solve(){
  80.     string L , R;
  81.     cin >> L >> R;
  82.     int ans = sub(calc(R) , calc(L));
  83.     if (check(L)) self_add(ans , 1);
  84.     cout << ans << "\n";
  85. }
  86.  
  87. #define name "R"
  88.  
  89. int main(){
  90.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  91.     if (fopen(name".INP" , "r")){
  92.         freopen(name".INP" , "r" , stdin);
  93.         freopen(name".OUT" , "w" , stdout);
  94.     }
  95.     p[0] = 1;
  96.     for (int i = 1 ; i < maxN ; i++) p[i] = (p[i - 1] * 10) % 19;
  97.     memset(dp , -1 , sizeof(dp));
  98.     int t = 1; cin >> t;
  99.     while (t--) solve();
  100.     return 0;
  101. }
  102.  
  103.  
Success #stdin #stdout 0.01s 31812KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/nQq555
language:
C++ (gcc 8.3)
created:
1 day 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!