状压$+$数位$DP$
一个比较显然的做法是开两个$mask$分别表示每位是否出现和出现次数奇偶性,很不幸本题在$acwing$只有$64MB$空间,于是使用三进制状压,每位是$0/1/2$表示对应数字没出现/出现奇数次/出现偶数次即可。
#include <iostream>
#include <cstring>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
i64 f[21][60000];
int nums[21], len;
int p3[11];
int get(int x, int y) {
return x % p3[y + 1] / p3[y];
}
int set(int x, int y, int v) {
int t = get(x, y);
return x + (v - t) * p3[y];
}
bool check(int mask) {
for (int i = 0; i < 10; i++) {
if (i & 1) {
if (get(mask, i) == 1) {
return false;
}
}
else {
if (get(mask, i) == 2) {
return false;
}
}
}
return true;
}
i64 dfs(int pos, int lim, int lead, int mask) {
if (!pos) return check(mask);
i64& v = f[pos][mask];
if (~v && !lim && !lead) return v;
int upper = lim ? nums[pos] : 9;
i64 res = 0;
for (int i = 0; i <= upper; i++) {
int new_mask;
if (lead & !i) new_mask = 0;
else if (get(mask, i) % 2 == 0) new_mask = set(mask, i, 1);
else if (get(mask, i) == 1) new_mask = set(mask, i, 2);
res += dfs(pos - 1, lim & i == upper, lead & !i, new_mask);
}
return lim ? res : (lead ? res : v = res);
}
i64 dp(u64 n) {
len = 0;
while (n) nums[++len] = n % 10, n /= 10;
return dfs(len, 1, 1, 0);
}
void solve() {
u64 l, r;
cin >> l >> r;
cout << dp(r) - dp(l - 1) << '\n';
}
int main() {
int T;
cin >> T;
p3[0] = 1;
for (int i = 1; i <= 10; i++) p3[i] = p3[i - 1] * 3;
memset(f, -1, sizeof f);
while (T--) solve();
return 0;
}
%%%%%%
这个012真绝,我还一直想咋区别偶数出现0次和偶数次的区别呢