Advertisement
Guest User

Untitled

a guest
Feb 19th, 2016
6,801
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. const int INF = int(1e9);
  24. const li INF64 = li(1e18);
  25. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  26.  
  27. int m, d;
  28. string a, b;
  29.  
  30. inline bool read() {
  31.     if (!(cin >> m >> d)) return false;
  32.     assert(cin >> a >> b);
  33.     return true;
  34. }
  35.  
  36. const int mod = 1000 * 1000 * 1000 + 7;
  37.  
  38. inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
  39. inline void inc(int& a, int b) { a = add(a, b); }
  40. inline int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
  41. inline void dec(int& a, int b) { a = sub(a, b); }
  42.  
  43. const int N = 2020;
  44.  
  45. int z[N][N][2];
  46.  
  47. int solve(string s) {
  48.     int n = sz(s);
  49.     forn(i, n + 1) forn(j, m) forn(k, 2) z[i][j][k] = 0;
  50.     z[0][0][1] = 1;
  51.     forn(i, n)
  52.         forn(j, m)
  53.             forn(k, 2)
  54.                 for (int p = 0; p <= (k ? int(s[i] - '0') : 9); p++) {
  55.                     if ((i & 1) && p != d) continue;
  56.                     if (!(i & 1) && p == d) continue;
  57.                     if (!i && !p) continue;
  58.                     int ni = i + 1;
  59.                     int nj = (j * 10 + p) % m;
  60.                     int nk = k && (p == int(s[i] - '0'));
  61.                     inc(z[ni][nj][nk], z[i][j][k]);
  62.                 }
  63.     int ans = 0;
  64.     forn(k, 2) inc(ans, z[n][0][k]);
  65.     return ans;
  66. }
  67.  
  68. bool good(string s) {
  69.     int rm = 0;
  70.     forn(i, sz(s)) {
  71.         int p = int(s[i] - '0');
  72.         if ((i & 1) && p != d) return false;
  73.         if (!(i & 1) && p == d) return false;
  74.         rm = (rm * 10 + p) % m;
  75.     }
  76.     return !rm;
  77. }
  78.  
  79. inline void solve() {
  80.     int ans = 0;
  81.     inc(ans, solve(b));
  82.     dec(ans, solve(a));
  83.     inc(ans, good(a));
  84.     cout << ans << endl;
  85. }
  86.  
  87. inline ld gett() { return ld(clock()) / CLOCKS_PER_SEC; }
  88.  
  89. int main() {
  90. #ifdef SU1
  91.     assert(freopen("input.txt", "rt", stdin));
  92.     //assert(freopen("output.txt", "wt", stdout));
  93. #endif
  94.    
  95.     cout << setprecision(10) << fixed;
  96.     cerr << setprecision(5) << fixed;
  97.  
  98.     while (read()) {
  99.         ld stime = gett();
  100.         solve();
  101.         cerr << gett() - stime << endl;
  102.     }
  103.    
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement