fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL);
  4. #define FF first
  5. #define SS second
  6. #define eps 1e-9
  7. #define PI aocs(-1.0)
  8. // VECTOR (6)
  9. #define pb push_back
  10. #define sz(x) (int)x.size()
  11. #define all(x) (x).begin(), (x).end()
  12. #define lb lower_bound
  13. #define ub upper_bound
  14. #define uniq(x) sort(all((x))), (x).resize(unique(all((x))) - (x).begin());
  15. // BIT (6)
  16. #define BIT(x, i) (((x)>>(i))&1)
  17. #define MASK(i) (1LL<<(i))
  18. #define CNTBIT(x) __builtin_popcountll(x)
  19. #define ODDBIT(x) __builtin_parityll(x)
  20. #define SUBSET(big, small) (((big)&(small))==(small))
  21. #define FIRSTBIT(x) __builtin_ctzll(x)
  22. //typedef
  23. typedef long long ll;
  24. typedef unsigned long long ull;
  25. typedef long double ld;
  26. typedef pair<ll, int> ii;
  27.  
  28. /* */
  29. template <class T>
  30. bool minimize(T &a, const T &b) {
  31.     if(a > b) {a = b; return 1;}
  32.     return 0;
  33. }
  34. template <class T>
  35. bool maximize(T &a, const T &b) {
  36.     if(a < b) {a = b; return 1;}
  37.     return 0;
  38. }
  39. /* */
  40.  
  41. /* CODE BELOW */
  42. const int N = 1e5 + 7, M = 1e9 + 7;
  43. const int MOD = 1e9 + 7;
  44. const int oo = 1e9 + 7;
  45.  
  46. /* */
  47.  
  48. int add(int a, int b) {
  49.     a+= b; if(a>=MOD) a-=MOD;
  50.     return a;
  51. }
  52. void update(int &a, int b) {
  53.     a+= b; if(a>=MOD) a-=MOD;
  54. }
  55.  
  56. /* */
  57.  
  58. vector<int> l, r, k;
  59. int n, kmp[N];
  60. int nxt[N][10];
  61. vector<vector<int> > _dp[2][2];
  62.  
  63. int solve(const vector<int> &num, int tightness, int kExist, int idx, int suffixMatch) {
  64.     if(idx == sz(num)) return kExist;
  65.     int &ans = _dp[tightness][kExist][idx][suffixMatch];
  66.     if(ans != -1) return ans; ans = 0;
  67.  
  68.     for(int i=0;i<10;i++) {
  69.         if(tightness && i > num[idx]) break;
  70.         update(ans, solve(num, (num[idx] == i)&tightness, kExist | (nxt[suffixMatch][i] == n), idx+1, nxt[suffixMatch][i]%n));
  71.     }
  72.     //update(ans, kExist);
  73.  
  74.     //cout<<tightness<<" "<<kExist<<" "<<idx<<" "<<suffixMatch<<" = "<<ans<<"\n";
  75.     return ans;
  76. }
  77.  
  78. signed main() {
  79.     //freopen("test.inp", "r", stdin);
  80.     //freopen("test.out", "w", stdout);
  81.     fastIO;
  82.     string _l, _r, _k;
  83.     cin>>_l>>_r>>_k; n = sz(_k);
  84.     for(char c:_l) l.pb(c-'0');
  85.     for(char c:_r) r.pb(c-'0');
  86.     for(char c:_k) k.pb(c-'0');
  87.  
  88.  
  89.     for(int i=sz(l)-1;i>=0;i--) {
  90.         l[i]--; if(l[i] >= 0) break;
  91.         l[i] = 9;
  92.     }
  93.  
  94.     for(int j, i=1;i<n;i++) {
  95.         j = kmp[i-1];
  96.         while(j > 0 && k[i] != k[j]) j = kmp[j-1];
  97.         if(k[i] == k[j]) j++; kmp[i] = j;
  98.     }
  99.  
  100.     for(int i=0;i<n;i++) {
  101.         for(int j=0;j<10;j++) {
  102.             if(k[i] == j) nxt[i][j] = i + 1;
  103.             else if (i > 0) nxt[i][j] = nxt[kmp[i-1]][j];
  104.         }
  105.     }
  106.  
  107.     for(int i=0;i<2;i++) {
  108.         for(int j=0;j<2;j++) {
  109.             _dp[i][j].resize(sz(r));
  110.             for(int l=0;l<sz(r);l++) {
  111.                 _dp[i][j][l].assign(min(l, n)+1, -1);
  112.             }
  113.         }
  114.     }
  115.     int ansL = solve(l, 1, 0, 0, 0);
  116.  
  117.     for(int i=0;i<2;i++) {
  118.         for(int j=0;j<2;j++) {
  119.             for(int l=0;l<sz(r);l++) {
  120.                 _dp[i][j][l].assign(min(l, n)+1, -1);
  121.             }
  122.         }
  123.     }
  124.     int ansR = solve(r, 1, 0, 0, 0);
  125.  
  126.     cout<<add(ansR, MOD - ansL);
  127.  
  128.     return 0;
  129. }
Success #stdin #stdout 0.01s 5360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8g51QE
Beauty number
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!