https://codeforces.com/contest/628/problem/D
题目大意
给出 $m \ (1 \le m \le 2000)$ 和数字 $d \ (0 \le d \le 9)$，给出两个字符串表示的没有前导零的大整数 $a, b \ (1 \le a \le b \le 10^2000)$。 问在区间 $[a, b]$ 中有多少数字 $x$ 符合能被 $m$ 整除，且从高向低数的偶数位（$1-based$）,都是 $d$ 且奇数位都不是 $d$。
简要题解
一眼数位 dp，分比较高可能是因为比赛里面确实比较难较快的写完或者调出来。
考虑 $dp[cur][rm][odd \ 0/1][lim \ 0/1][zero \ 0/1]$ 表示当前考虑了高 $cur + 1$ 位，目前余数是 $rm$，去除前导零后当前位是 $odd$ 奇数位（对应题中 $1-based$ 的偶数位），顶到了上限 $lim$，之前的位都是前导零 $zero$。转移比较直观，详见代码。
特别注意：这题因为状态开的比较满，因此如果开得变量比较随性的话，可能喜提 MLE。以下为某 MLE 部分代码。简单计算它至少用了 $384MB$ 的空间，超出了 $256MB$ 的限制。
const int MM = 2000;
const int MN = 2000;
bool check(string s, int m, int d) {
int cur = 0;
for (char c : s) {
cur = (cur * 10 + c - '0') % m;
}
if (cur) return false;
int n = s.length();
for (int i = 1; i < n; i += 2) {
if (s[i] - '0' != d) return false;
}
for (int i = 0; i < n; i += 2) {
if (s[i] - '0' == d) return false;
}
return true;
}
Mint dp[MN][MM][2][2][2]; // struct { long long x; }
int vis[MN][MM][2][2][2]; // 384,000,000
vector<int> a;
int n, m, d;
Mint dfs(int cur, int rm, int odd, int lim, int zero) {
if (cur == n) {
return !zero && rm == 0;
}
if (vis[cur][rm][odd][lim][zero]) {
return dp[cur][rm][odd][lim][zero];
}
vis[cur][rm][odd][lim][zero] = 1;
Mint& ans = dp[cur][rm][odd][lim][zero];
ans = 0;
int up = lim ? a[cur] : 9;
if (zero) {
ans += dfs(cur + 1, 0, 0, 0, 1);
for (int i = 1; i <= up; i++) {
if (i == d) continue;
ans += dfs(cur + 1, i % m, 1, lim && i == up, 0);
}
return ans;
}
// zero false!
if (odd) { // need to fill a d
if (lim) {
if (a[cur] < d) {
ans = Mint(0);
} else {
ans = dfs(cur + 1, (rm * 10 + d) % m, 0, d == up, 0);
}
} else {
ans = dfs(cur + 1, (rm * 10 + d) % m, 0, 0, 0);
}
} else {
for (int i = 0; i <= up; i++) {
if (i == d) continue;
ans += dfs(cur + 1, (rm * 10 + i) % m, 1, lim && i == up, 0);
}
}
return ans;
}
Mint solve(string s, int mm, int dd) {
n = s.length();
m = mm;
d = dd;
a.clear();
for (char c : s) {
a.push_back(c - '0');
}
memset(vis, 0, sizeof(vis));
Mint ans = dfs(0, 0, 0, 1, 1);
// cerr << s << ' ' << mm << ' ' << dd << ' ' << ans << endl;
return ans;
}
void solve() {
int m, d; cin >> m >> d;
string a, b; cin >> a >> b;
cout << (solve(b, m, d) - solve(a, m, d) + check(a, m, d)) << '\n';
}
复杂度
$T$：$O(|B| m)$
$S$：$O(|B| m)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int MO = 1e9 + 7;
inline void addv(int& x, int y) {
x += y;
if (x >= MO) x -= MO;
}
inline void subv(int& x, int y) {
x -= y;
if (x < 0) x += MO;
}
const int MM = 2000;
const int MN = 2000;
bool check(string s, int m, int d) {
int cur = 0;
for (char c : s) {
cur = (cur * 10 + c - '0') % m;
}
if (cur) return false;
int n = s.length();
for (int i = 1; i < n; i += 2) {
if (s[i] - '0' != d) return false;
}
for (int i = 0; i < n; i += 2) {
if (s[i] - '0' == d) return false;
}
return true;
}
int dp[MN][MM][2][2][2];
vector<int> a;
int n, m, d;
int dfs(int cur, int rm, int odd, int lim, int zero) {
if (cur == n) {
return !zero && rm == 0;
}
if (dp[cur][rm][odd][lim][zero] != -1) {
return dp[cur][rm][odd][lim][zero];
}
int& ans = dp[cur][rm][odd][lim][zero];
ans = 0;
int up = lim ? a[cur] : 9;
if (zero) {
addv(ans, dfs(cur + 1, 0, 0, 0, 1));
for (int i = 1; i <= up; i++) {
if (i == d) continue;
addv(ans, dfs(cur + 1, i % m, 1, lim && i == up, 0));
}
return ans;
}
// zero false!
if (odd) { // need to fill a d
if (lim) {
if (a[cur] < d) {
ans = 0;
} else {
ans = dfs(cur + 1, (rm * 10 + d) % m, 0, d == up, 0);
}
} else {
ans = dfs(cur + 1, (rm * 10 + d) % m, 0, 0, 0);
}
} else {
for (int i = 0; i <= up; i++) {
if (i == d) continue;
addv(ans, dfs(cur + 1, (rm * 10 + i) % m, 1, lim && i == up, 0));
}
}
return ans;
}
int solve(string s, int mm, int dd) {
n = s.length();
m = mm;
d = dd;
a.clear();
for (char c : s) {
a.push_back(c - '0');
}
memset(dp, -1, sizeof(dp));
int ans = dfs(0, 0, 0, 1, 1);
// cerr << s << ' ' << mm << ' ' << dd << ' ' << ans << endl;
return ans;
}
void solve() {
int m, d; cin >> m >> d;
string a, b; cin >> a >> b;
int ans = solve(b, m, d);
subv(ans, solve(a, m, d));
addv(ans, check(a, m, d));
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. New Skateboard - Educational Codeforces Round 8