trungore10

Untitled

Apr 11th, 2021
438
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2004, MOD = 1e9+7;
  5. int m, d;
  6. string l, r;
  7.  
  8. int num, a[N], b[N], dp[N][N][2][2];
  9.  
  10. int calc(int pos, int mod, int flag, int flag2) {
  11.     if (pos == num+1) return (mod == 0);
  12.  
  13.     int &foo = dp[pos][mod][flag][flag2];
  14.     if (foo != -1) return foo; foo = 0;
  15.  
  16.     int Begin, End;
  17.     if (pos % 2 == 0) {
  18.         Begin = End = d;
  19.         if (d < a[pos] && !flag) return 0;
  20.         if (d > b[pos] && !flag2) return 0;
  21.     }
  22.     else {
  23.         Begin = (flag) ? 0 : a[pos];
  24.         End = (flag2) ? 9 : b[pos];
  25.     }
  26.  
  27.         // cerr << pos << " " << mod << " " << flag << " " << flag2 << " --> " << Begin << " " << End << '\n';
  28.  
  29.     for (int dig = Begin; dig <= End; ++dig) {
  30.         if (pos % 2 == 1 && dig == d) continue;
  31.         int nMod = (mod * 10 + dig) % m;
  32.         int nFlag  = ( flag | (dig>a[pos]) );
  33.         int nFlag2 = ( flag2 | (dig<b[pos]) );
  34.         foo += calc(pos+1, nMod, nFlag, nFlag2); foo %= MOD;
  35.     }
  36.    
  37.     return foo;
  38. }
  39.  
  40. int process() {
  41.     num = (int) l.length();
  42.     for (int i = 1; i <= num; ++i) a[i] = l[i-1] - '0';
  43.     for (int i = 1; i <= num; ++i) b[i] = r[i-1] - '0';
  44.  
  45.     memset(dp, -1, sizeof(dp));
  46.     int res = calc(1, 0, 0, 0);
  47.     return res;
  48. }
  49.  
  50. int check(string lim) {
  51.     return 0;
  52.     int mod = 0; bool ok = true;
  53.     for (int i = 0; i < (int) lim.length(); ++i) {
  54.         mod = (mod * 10 + lim[i] - '0') % m;
  55.         if (i % 2 == 1 && lim[i] - '0' != d) { ok = false; break; }
  56.     }
  57.     return (ok && mod == 0);
  58. }
  59.  
  60. int main() {
  61.     //freopen("input.txt", "r", stdin);
  62.  
  63.     cin >> m >> d >> l >> r;
  64.     int res = (process() + check(l)) % MOD;
  65.     cout << res << '\n';
  66.  
  67.     return 0;
  68. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×