专栏文章

题解：P11799 【MX-X9-T3】『GROI-R3』Powerless

EEngulf
P11799题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mio18yk3
此快照首次捕获于
2025/12/02 11:42
3 个月前
此快照最后确认于
2025/12/02 11:42
3 个月前
查看原文
提供一种好想好写的做法！
∑i=1n∑j=1n∑k=0mmin⁡(ai⊕k,aj⊕k)\sum_{i=1}^n\sum_{j=1}^n\sum_{k=0}^m \min(a_i \oplus k, a_j \oplus k)
要拆掉 min⁡\min。
  • 如果 ai=aja_i = a_j，那么 ai⊕k=aj⊕ka_i\oplus k = a_j \oplus k，min⁡\min 就可以去掉。记录数 xx 的出现次数 cxc_x，对于同一类，两两之间的贡献是 cx2∑k=0mx⊕kc_x^2\sum\limits_{k=0}^m x\oplus k。
  • 如果 ai≠aja_i \neq a_j，发现 (i,j)(i, j) 和 (j,i)(j, i) 的贡献是相等的，可以在取最小值的位置计算贡献，最后 ×2\times 2 即可。不妨设 ai⊕k<aj⊕ka_i \oplus k < a_j \oplus k，那么贡献在 ii 处计算，这部分的贡献是 2∑i=1n∑k=0m(ai⊕k)[ai⊕k<aj⊕k]2\sum\limits_{i=1}^n \sum\limits_{k=0}^m(a_i \oplus k)[a_i\oplus k < a_j \oplus k]。
现在我们要计算
2∑i=1n∑k=0m(ai⊕k)[ai⊕k<aj⊕k]+cx2∑k=0mx⊕k2\sum_{i=1}^n \sum_{k=0}^m(a_i \oplus k)[a_i\oplus k < a_j \oplus k] + c_x^2\sum\limits_{k=0}^m x\oplus k
先考虑第一项：
2∑i=1n∑k=0m(ai⊕k)[ai⊕k<aj⊕k]2\sum_{i=1}^n \sum_{k=0}^m(a_i \oplus k)[a_i\oplus k < a_j \oplus k]
记 msb(x)\textrm{msb}(x) 表示 xx 的最高有效位，xkx_k 表示 xx 在二进制下的第 kk 位。
发现影响 ai⊕ka_i \oplus k 和 aj⊕ka_j \oplus k 大小的是 msb(ai⊕k)\textrm{msb}(a_i \oplus k) 和 msb(aj⊕k)\textrm{msb}(a_j \oplus k)，也就取决于两数在第 msb((ai⊕k)⊕(aj⊕k))=msb(ai⊕aj)\textrm{msb}\left((a_i \oplus k) \oplus (a_j \oplus k)\right) = \textrm{msb}\left(a_i \oplus a_j\right) 位的值。和 kk 无关。
令 c=msb(ai⊕aj)c = \textrm{msb}(a_i \oplus a_j)，这意味着 aic≠ajc{a_i}_c \neq {a_j}_c，所以能贡献的 kk 一定满足 kc=aick_c = {a_i}_c，这样，(ai⊕k)c=0,(aj⊕k)c=1(a_i\oplus k)_c = 0, (a_j \oplus k)_c = 1，所以一定有 ai⊕k<aj⊕ka_i\oplus k < a_j \oplus k。
枚举 aia_i 和 cc，这部分的贡献可以写成
2(∑j=1n[msb(ai⊕aj)=c])(∑k=0m(ai⊕k)[aic=kc])2\left(\sum_{j=1}^n[\textrm{msb}(a_i \oplus a_j) = c]\right)\left(\sum_{k=0}^m(a_i \oplus k)[{a_i}_c = k_c]\right)
左边括号的值，相当于求 (c,29](c, 29] 位都与 aia_i 相同，第 cc 位不同的数的个数。可以把所有 aa 插入 01 trie，就变成求子树大小。记为 szsz。
右边括号的值，拆位，对于第 jj 位，所有满足 aij≠kj{a_i}_j \neq k_j 且 aic=kc{a_i}_c = k_c 的 kk 都能产生 2j2^j 的贡献。
考虑预处理数组 fi,j,0/1,0/1f_{i, j, 0/1, 0/1} 表示 [0,m][0, m] 中满足 ki=0/1,kj=0/1k_i = 0/1, k_j = 0/1 的 kk 的个数。可以用数位 dp 求出。
2(∑j=1n[msb(ai⊕aj)=c])(∑j=0292jfj,c,aij⊕1,aic)2\left(\sum_{j=1}^n[\textrm{msb}(a_i \oplus a_j) = c]\right)\left(\sum_{j=0}^{29}2^jf_{j, c, {a_i}_j\oplus 1, {a_i}_c}\right)
再考虑第二项：
cx2∑k=0mx⊕kc_x^2\sum\limits_{k=0}^m x\oplus k
这就容易多了，一样的思路，拆位，对于第 jj 位，所有满足 xj≠kjx_j \neq k_j 的 kk 都能产生 2j2^j 的贡献。利用预处理好的 ff 数组。
cx2∑j=0292jfj,j,xj⊕1,xj⊕1c_x^2\sum\limits_{j=0}^{29} 2^jf_{j, j, x_j \oplus 1, x_j\oplus 1}
加起来就是最终的答案：
2∑i=1n∑c=029sz(∑j=0292jfj,c,aij⊕1,aic)+∑xcx2∑j=0292jfj,j,xj⊕1,xj⊕1\boxed{2\sum_{i=1}^n\sum_{c=0}^{29}sz\left(\sum_{j=0}^{29}2^jf_{j, c, {a_i}_j\oplus 1, {a_i}_c}\right) + \sum_xc_x^2\sum\limits_{j=0}^{29} 2^jf_{j, j, x_j \oplus 1, x_j\oplus 1}}
Θ(nlog⁡2V)\Theta(n\log^2V)，其中 VV 是值域大小。
实现CPP
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

constexpr int N = 2e5 + 5, mod = 998244353;

int n, m;
int a[N];

unordered_map<int, int> mp;

int tr[N * 29][2], idx;
int siz[N * 29];

void insert(int x) {
    int p = 0;
    for (int i = 29; i >= 0; i--) {
        int v = x >> i & 1;
        if (!tr[p][v]) tr[p][v] = ++idx;
        p = tr[p][v];
    }
    siz[p]++;
}

void dfs(int u) {
    if (!u) return;
    for (int i = 0; i <= 1; i++) {
        dfs(tr[u][i]);
        siz[u] += siz[tr[u][i]];
    }
}

int f[30][30][2][2]; // f[i][j][0 / 1][0 / 1] k \in [0, m] 且使得 k 第 i 位为 0/1，第 j 位为 0/1 的 k 的数量

int dp[30];

int dfs(int pos, int p1, int p2, int v1, int v2, int lim) {
    if (pos == -1) return 1;
    if (!lim && ~dp[pos]) return dp[pos];

    int res = 0;
    for (int i = 0; i <= (lim ? m >> pos & 1 : 1); i++) {
        if (pos == p1 && i != v1) continue;
        if (pos == p2 && i != v2) continue;
        res += dfs(pos - 1, p1, p2, v1, v2, lim && (i == (m >> pos & 1)));
    }

    return lim ? res : dp[pos] = res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]]++;
        insert(a[i]);
    }

    sort(a + 1, a + 1 + n);

    for (int i = 0; i <= 29; i++)
        for (int j = 0; j <= 29; j++)
            for (int v1 = 0; v1 <= 1; v1++)
                for (int v2 = 0; v2 <= 1; v2++) {
                    memset(dp, -1, sizeof dp);
                    f[i][j][v1][v2] = dfs(29, i, j, v1, v2, 1);
                }

    for (int i = 0; i <= 1; i++)
        if (tr[0][i])
            dfs(tr[0][i]);

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        int x = a[i];
        for (int c = 0; c <= 29; c++) {
            int p = 0;
            for (int j = 29; j > c; j--) p = tr[p][x >> j & 1];
            int sz = siz[tr[p][!(x >> c & 1)]];
            int con = 0;

            for (int j = 0; j <= 29; j++)
                con = (con + 1ll * (1 << j) * f[j][c][!(x >> j & 1)][x >> c & 1]) % mod;

            ans = (ans + 1ll * sz * con) % mod;
        }
    }

    ans = 1ll * ans * 2 % mod;

    n = unique(a + 1, a + 1 + n) - a - 1;
    for (int i = 1; i <= n; i++) {
        int res = 0;
        for (int j = 0; j <= 29; j++) {
            int v = a[i] >> j & 1;
            res = (res + 1ll * (1 << j) * f[j][j][v ^ 1][v ^ 1]) % mod;
        }
        ans = (ans + 1ll * mp[a[i]] * mp[a[i]] % mod * res) % mod;
    }

    cout << ans << "\n";

    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...