题解：CF1245F Daniel and Spring Cleaning

2huk · 2024-05-22 15:14:07 · 题解

• 给定 l, r，求 \sum_{i=l}^r \sum_{j=l}^r [i+j = i \operatorname{xor} j]。

因为异或是不进位加法，所以只要 i, j 进行加法时不进位，就一定有 i+j = i \operatorname{xor} j。换言之，i \operatorname{and} j = 0 和 i+j = i \operatorname{xor} j 是等价的。

所以所求即 \sum_{i=l}^r \sum_{j=l}^r [i \operatorname{and} j = 0]。

设 f(x, y) = \sum_{i=\color{red}1}^x \sum_{j=\color{red}1}^y [i \operatorname{and} j = 0]。那么所求即 f(r, r) - f(r, l - 1) - f(l - 1, r) + f(l - 1, l - 1)。f(x, y) 的求解是简单数位 DP。

int dp(int u, bool sb, bool bs) {
    if (!u) return 1;

    int& res = f[u][sb][bs];
    if (~res) return res;
    res = 0;

    int t1 = sb ? a[u] : 1;
    int t2 = bs ? b[u] : 1;

    for (int i = 0; i <= t1; ++ i )
        for (int j = 0; j <= t2; ++ j )
            if (!i || !j) res += dp(u - 1, sb && (i == t1), bs && (j == t2));

    return res;
}

int calc(int x, int y) {
    if (x < 0 || y < 0) return 0;

    memset(f, -1, sizeof f);
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);

    int l = 0;
    while (x) {
        a[ ++ l] = x & 1;
        x >>= 1;
    }
    len = l, l = 0;
    while (y) {
        b[ ++ l] = y & 1;
        y >>= 1;
    }
    len = max(len, l);

    int res = dp(len, 1, 1);

    return dp(len, 1, 1);
}

void Luogu_UID_748509() {
    int l, r;
    fin >> l >> r;
    fout << (calc(l - 1, l - 1) + calc(r, r)) - (calc(l - 1, r) + calc(r, l - 1)) << '\n';
}