628D - Magic Numbers - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (int i=0;i<a.size();i++) cin>>a[i]; return cin; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
typedef long long ll;

#define debug if (0) cout

int m, d;
ll dp[2002][2][2][2002]; // pos, odd/even, /smaller, m remainder
string value;
constexpr ll MOD = 1000000007;

ll calculate(int pos, int isEven, int isSmaller, int r) {
  if (pos == value.size()) {
    return r == 0 ? 1 : 0;
  }
  
  if (dp[pos][isEven][isSmaller][r] >= 0) {
    return dp[pos][isEven][isSmaller][r];
  }

  int upLimit = isSmaller ? 9 : (value[pos] - '0');
  
  dp[pos][isEven][isSmaller][r] = 0;
  if (isEven) {
    if (d > upLimit) {
      // could not chose d;
      return dp[pos][isEven][isSmaller][r] = 0;
    }
    dp[pos][isEven][isSmaller][r] +=
        calculate(pos + 1, 1 - isEven, isSmaller || d < (value[pos] - '0'), (r * 10 + d) % m);
    dp[pos][isEven][isSmaller][r] %= MOD;
  } else {
    for (int i = 0; i <= upLimit; i++) {
      if (i == d) continue;
      dp[pos][isEven][isSmaller][r] +=
          calculate(pos + 1, 1 - isEven, isSmaller || i < (value[pos] - '0'), (r * 10 + i) % m);
      dp[pos][isEven][isSmaller][r] %= MOD;
    }
  }

  return dp[pos][isEven][isSmaller][r];
}

ll solve(string v) {
  memset(dp, -1, sizeof(dp));
  value = v;

  ll ans = calculate(0, 0, 0, 0);
  debug << v << " : " << ans << endl;
  return ans;
}

int isOK(string a) {
  // check d-magic
  for (int i = 0; i < a.size(); i++) {
    if (i % 2 == 0) {
      // odd pos
      if (a[i] - '0' == d) {
        return 0; // false
      }
    } else {
      // even pos
      if (a[i] - '0' != d) {
        return 0; // false
      }
    }
  }
  
  // divisible 
  int v = 0;
  for (int i = 0; i < a.size(); i++) {
    v = (v * 10 + (a[i] - '0')) % m;
  }
  if (v == 0) return 1; else return 0;
}
void solve() {
  cin >> m >> d;
  string a, b;
  cin >> a >> b;
  
  ll ans = (solve(b) + MOD - solve(a) + isOK(a)) % MOD;
  cout << ans << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int cases = 1;
  // cin >> cases;
  for (int i = 0; i < cases; i++) {
    debug << "cases : " << i + 1 << endl;
    solve();
    debug << endl;
  }
  
  return 0;
}