UOJ Logo faaaaaa的博客

博客

Balanced Numbers

2020-05-19 15:27:53 By faaaaaa

$Solution$

每个数字有三种状态:未出现,出现奇数次,出现偶数次。

我们把0-9的每个数代表每个三进制位,三进制位就表示其三个状态,状态压缩就好了。状态数是 $3^9=59049$。开的下。

$Code$

#include <cstdio>
#include <cstring>
typedef long long ll;

ll dp[20][60000], a[20], t[20];

ll read() {
    ll x = 0, f = 1; char s;
    while((s = getchar()) < '0' || s > '9') if(s == '-') f = -1;
    while(s >= '0' && s <= '9') {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
    return x * f;
}

bool check(int s) {
    int d;
    for(int i = 0; i < 10; ++ i) {
        d = s % 3; s /= 3;
        if(! d) continue;
        if(d == 1 && (i & 1)) return 0;
        if(d == 2 && (i & 1) == 0) return 0;
    }
    return 1;
}

int Get(const int p, int s) {
    for(int i = 0; i < 10; ++ i) {
        t[i] = s % 3;
        s /= 3;
    }
    s = 0;
    if(t[p] == 0) t[p] = 1;
    else t[p] = 3 - t[p];
    for(int i = 9; i >= 0; -- i) s = s * 3 + t[i];
    return s;
}

ll DP(const int p, const ll s, const bool f, const bool lim) {
    if(p == -1) return check(s);
    if(! lim && (~ dp[p][s])) return dp[p][s];
    int up = lim ? a[p] : 9;
    ll ans = 0;
    for(int i = 0; i <= up; ++ i)
        ans += DP(p - 1, (! f && i == 0) ? 0 : Get(i, s), f || i > 0, lim && i == a[p]);
    if(! lim) dp[p][s] = ans;
    return ans;
}

ll get(ll x) {
    int pos = -1;
    while(x) {
        a[++ pos] = x % 10;
        x /= 10;
    }
    return DP(pos, 0, 0, 1);
}

int main() {
    int T = read(); ll l, r;
    memset(dp, -1, sizeof dp);
    while(T --) {
        l = read(), r = read();
        printf("%lld\n", get(r) - get(l - 1));
    }
    return 0;
}
faaaaaa Avatar