SP10606 BALNUM - Balanced Numbers 题解

WWFZZZ · 2022-02-13 14:34:00 · 题解

只能说，数位 dp 的题目用记忆化搜索写起来真的十分方便。

我们来想这么一个问题：如何简单的表示一个数中所有数字出现个数的奇偶性这一状态？

你可能会说，状压呗。先用一个二进制数 s1 表示所有数是否出现，再用 s2 来表示所有数出现次数的奇偶性。但是，这样的话，我们算一下总共的计算量，大概是 19 \times 1024 \times 1024 = 19922944，本题时限只有 123 毫秒，一般情况下是过不了的。

那我们要从哪里开始优化呢？

首先，一个数的状态最多只有 3 种，要么没出现，要么出现了偶数次，要么出现了奇数次。所以说，我们可以用一个三进制状态来保存。而刚刚那种做法相当于是四进制，就十分浪费。采用优化的算法后，计算量约为 19\times3 ^ {10}= 1121931，完全可以过。那么，我们就可以使用记忆化搜索，代码也很好想了。当然，要对前导 0 引起相当的注意。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[20], n, p[10];
inline int get_state(int state, int x) {
    if (state / p[x] % 3 == 2) state -= p[x];
    else if (state / p[x] % 3 == 1) state += p[x];
    else state += p[x];
    return state;
}
inline bool check_state(int state) {
    for (int i = 0; i < 10; ++i)
        if (state / p[i] % 3) {
            int y = state / p[i] % 3;
            if ((y & 1) == (i & 1)) return 0;
        }
    return 1;
}
LL f[20][59049][2];
LL dfs(int pos, int state, bool limit, bool zero) {
    if (pos == 0) return check_state(state);
    if (!limit && ~f[pos][state][zero]) return f[pos][state][zero];
    LL res = 0;
    for (int i = 0; i <= (limit ? a[pos] : 9); ++i) 
        res += dfs(pos - 1, zero && !i ? 0 : get_state(state, i), limit && (i == a[pos]), zero && !i);
    if (!limit) f[pos][state][zero] = res;
    return res;
}
LL calc(LL X) {
    n = 0;
    while (X) a[++n] = X % 10, X /= 10;
    return dfs(n, 0, 1, 1);
}
int main() {
    int T;
    memset(f, -1, sizeof f);
    p[0] = 1;
    for (int i = 1; i < 10; ++i) p[i] = p[i - 1] * 3;
    scanf("%d", &T);
    while (T--) {
        LL L, R;
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", calc(R) - calc(L - 1));
    }
}