ExclusiveOR - 题解

标签与难度

标签: FWT, XOR卷积, 位运算, 快速幂, 动态规划, 优化 难度: 2300

题目大意喵~

主人你好呀~！这道题是这样的：

我们有一个包含 $n$ 个整数的集合 $A = \{A_1, A_2, \dots, A_n\}$。对于从 1 到 $n$ 的每一个整数 $i$，我们需要从集合 $A$ 中可重复地挑选出恰好 $i$ 个数，然后计算它们的异或和（XOR sum）。我们的任务是，对于每个 $i$，找出可以得到的最大的异或和是多少，喵~

最后，我们要按顺序输出这 $n$ 个最大值。

举个栗子，如果 $A = \{6, 1\}$ 且 $n=3$：

• 当 $i=1$ 时，我们可以选 6 或者 1。最大的当然是 6 啦。
• 当 $i=2$ 时，我们可以选 $\{6,6\}, \{6,1\}, \{1,1\}, \{1,6\}$。它们的异或和分别是 $6 \oplus 6 = 0$, $6 \oplus 1 = 7$, $1 \oplus 1 = 0$。最大的是 7。
• 当 $i=3$ 时，我们可以选 $\{6,6,6\}, \{6,6,1\}, \{6,1,1\}, \{1,1,1\}$ 等等。它们的异或和分别是 $6, 1, 6, 1$。最大的是 6。

所以对于这个例子，输出就是 6 7 6，你明白了吗，呐？

解题思路分析

这道题看起来是在问我们，用 $i$ 个数能凑出的最大异或和，而且 $i$ 还会变化。直接暴力枚举肯定是不行的，因为组合太多了，会 TLE 的说！所以我们需要一种更聪明的办法，喵~

从集合到多项式

我们可以换个角度看问题。对于一个数字集合，比如我们能凑出来的数字集合 $S$，我们可以用一个“特征多项式”（其实就是一个数组）来表示它。比如说，我们创建一个数组 P，如果数字 k 在集合 $S$ 中，我们就让 P[k] = 1，否则 P[k] = 0。

• $P_1$ 表示我们选 1 个数能凑出的所有值的集合。这不就是输入的集合 $A$ 嘛！所以，对于所有 $v \in A$，我们有 $P_1[v] = 1$。
• $P_2$ 表示我们选 2 个数能凑出的所有值的集合。一个在 $P_2$ 中的值 $k$ 是怎么来的呢？它肯定是 $a \oplus b$ 的结果，其中 $a$ 和 $b$ 都是从集合 $A$ 中选的，也就是 $a, b$ 都在 $P_1$ 所代表的集合里。
• 推广一下， $P_i$ 表示选 $i$ 个数能凑出的所有值的集合。一个在 $P_i$ 中的值 $k$ 是由一个在 $P_{i-1}$ 中的值 $u$ 和一个在 $P_1$ 中的值 $v$ 异或得到的，即 $k = u \oplus v$。

XOR 卷积与 FWT

上面这种通过异或操作来合并两个集合生成新集合的过程，在数学上被称为 XOR 卷积 (XOR Convolution)。两个多项式（数组）$F$ 和 $G$ 的 XOR 卷积 $H = F \otimes G$ 定义为：

$$H[k] = \sum_{i \oplus j = k} F[i] \cdot G[j]$$

在我们这道题里，我们只关心一个数能不能被凑出来，而不是有多少种凑法。所以我们可以把上面的公式理解为布尔运算：

$$H[k] = \bigvee_{i \oplus j = k} (F[i] \land G[j])$$

其中 $\bigvee$ 是逻辑或，$\land$ 是逻辑与。

这样一来，我们的问题就变成了：

• $P_2 = P_1 \otimes P_1$
• $P_3 = P_2 \otimes P_1 = P_1 \otimes P_1 \otimes P_1$
• ...
• $P_i = P_1 \otimes P_1 \otimes \dots \otimes P_1$ ($i$ 次卷积)

直接计算卷积是很慢的。但是，就像普通乘法卷积可以用快速傅里叶变换 (FFT) 来加速一样，XOR 卷积可以用一种叫做快速沃尔什-哈达玛变换 (Fast Walsh-Hadamard Transform, FWT) 的算法来加速！

FWT 的神奇之处在于，它能把多项式变换到另一个“频域”，在这个频域里，卷积运算变成了简单的逐点相乘 (element-wise product)！

令 $\hat{P}$ 表示 $P$ 经过 FWT 变换后的结果，我们有：

$$\widehat{A \otimes B} = \hat{A} \odot \hat{B}$$

其中 $\odot$ 表示逐点相乘。

于是，$\widehat{P_i} = (\widehat{P_1})^i$。这就可以用快速幂来计算了！不过这里 $i$ 是线性增长的，我们直接迭代就好。

算法流程

有了 FWT 这个强力工具，我们的算法就很清晰了，喵~

1. 初始化：确定一个足够大的数组大小 L，它必须是 2 的幂次，并且要大于所有输入数字的最大值。根据题目范围，L = 1 << 18 (即 $2^{18}$) 就很安全。我们创建一个数组 p1，大小为 L，对于输入的每个数 v，令 p1[v] = 1。这个 p1 就是我们一切的基础。

2. 首次变换：计算 p1 的 FWT，得到 fwt_p1。这个 fwt_p1 之后会反复使用。

3. 迭代计算：我们需要一个变量 current_fwt_poly 来存储当前计算到了第 $i$ 次卷积的 FWT 结果。

   • 初始化 current_fwt_poly = fwt_p1。
   • 对于 $i = 1, 2, \dots, n$： a. 对 current_fwt_poly 进行逆 FWT (IFWT)，得到真正的多项式 p_i。 b. 在 p_i 中从后往前找，第一个非零项的下标就是当选择 $i$ 个数时能凑出的最大异或和。记录下这个答案。 c. 为了计算下一次（$i+1$），我们将 current_fwt_poly 与 fwt_p1 逐点相乘，得到的结果就是 $\widehat{P_{i+1}}$。current_fwt_poly[j] = current_fwt_poly[j] * fwt_p1[j]。

一个重要的优化！

如果 $n$ 很大，比如 $2 \cdot 10^5$，每次都做一次 $O(L \log L)$ 的 FWT/IFWT 还是太慢了。这里有一个关键的观察，喵~

我们来分析一下奇数和偶数次选择的情况：

• 偶数次：选 2 个数能凑出的集合是 $S_2 = \{a \oplus b\}$。选 4 个数能凑出的集合是 $S_4 = \{a \oplus b \oplus c \oplus d\} = \{(a \oplus b) \oplus (c \oplus d)\}$。因为 $S_2$ 对异或运算是封闭的（它形成一个子空间），所以 $S_4$ 和 $S_2$ 是完全一样的！因此，对于所有偶数 $i \ge 2$，能凑出的数字集合都是一样的，最大值自然也一样。
• 奇数次：选 1 个数的集合是 $S_1$。选 3 个数的集合是 $S_3 = \{a \oplus b \oplus c\}$。我们可以把 $S_3$ 看作是 $S_1$ 和 $S_2$ 的异或组合。由于 $S_1 \subseteq S_3 \subseteq S_5 \dots$，这个奇数集合链条会不断增长或保持不变。因为总的数值空间是有限的，这个链条最终一定会稳定下来！这个过程非常快，通常在十几次迭代后就会稳定。

结论：答案序列在经过一小段初始部分后，会呈现出周期为 2 的规律！也就是说，ans[i] = ans[i-2] 对足够大的 i 成立。

所以，我们只需要完整计算前几十个（比如 30 个）答案，后面的答案直接根据 ans[i-2] 就可以推出来啦！这样，无论 $n$ 多大，我们的计算量都是一个常数，真是太棒了，喵~

代码实现

这是我根据上面的思路，精心为你准备的代码哦~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 使用 long long 来存储多项式的系数，防止计算过程中溢出
using int_poly = long long;
// 定义一个质数模数，以及 2 在模下的逆元
const int_poly MOD = 998244353;
const int_poly INV2 = 499122177; // (MOD + 1) / 2

// FWT 命名空间，把相关的函数都放在这里，喵~
namespace FWT {
    // is_inverse 为 false 表示正向 FWT，为 true 表示逆向 IFWT
    void fwt_xor(std::vector<int_poly>& poly, bool is_inverse) {
        int n = poly.size();
        for (int step = 1; step < n; step <<= 1) {
            for (int i = 0; i < n; i += (step << 1)) {
                for (int j = 0; j < step; ++j) {
                    int_poly u = poly[i + j];
                    int_poly v = poly[i + j + step];
                    poly[i + j] = (u + v) % MOD;
                    poly[i + j + step] = (u - v + MOD) % MOD;
                    if (is_inverse) {
                        poly[i + j] = (poly[i + j] * INV2) % MOD;
                        poly[i + j + step] = (poly[i + j + step] * INV2) % MOD;
                    }
                }
            }
        }
    }
}

int main() {
    // 加速输入输出，让程序跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // FWT 的大小必须是 2 的幂，并且大于所有可能的输入值
    // 2^18 = 262144，对于这题足够了
    const int FWT_SIZE = 1 << 18;

    // p1 是我们的基础多项式，表示只选1个数能到达的数字
    std::vector<int_poly> base_poly(FWT_SIZE, 0);
    int max_val = 0;
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        base_poly[val] = 1;
        max_val = std::max(max_val, val);
    }

    // 对基础多项式做 FWT
    std::vector<int_poly> fwt_base_poly = base_poly;
    FWT::fwt_xor(fwt_base_poly, false);

    // current_fwt_poly[k] = (fwt_base_poly[k])^i
    std::vector<int_poly> current_fwt_poly = fwt_base_poly;
    
    // 存储最终答案的数组
    std::vector<int> answers;
    answers.reserve(n);

    // 我们最多计算 K 次，后面的结果就呈现周期性了
    const int K = 30;

    for (int i = 1; i <= n; ++i) {
        // 如果已经计算了足够多的初始项，就利用周期性
        if (i > K) {
            answers.push_back(answers[i - 3]); // ans[i] = ans[i-2], answers是0-indexed
            continue;
        }

        // 把当前 FWT 结果逆变换回来，得到实际的多项式
        std::vector<int_poly> p_i = current_fwt_poly;
        FWT::fwt_xor(p_i, true);

        // 从大到小找到第一个可以凑出来的数
        int max_xor_sum = 0;
        for (int j = FWT_SIZE - 1; j >= 0; --j) {
            if (p_i[j] > 0) {
                max_xor_sum = j;
                break;
            }
        }
        answers.push_back(max_xor_sum);

        // 为下一次迭代做准备，将当前 FWT 结果与基础 FWT 结果逐点相乘
        if (i < n) {
            for (int j = 0; j < FWT_SIZE; ++j) {
                current_fwt_poly[j] = (current_fwt_poly[j] * fwt_base_poly[j]) % MOD;
            }
        }
    }

    // 输出所有答案
    for (int i = 0; i < n; ++i) {
        std::cout << answers[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";

    return 0;
}

复杂度分析

• 时间复杂度: $O(K \cdot L \log L)$, 其中 $L$ 是 FWT 的大小（这里是 $2^{18}$），$K$ 是我们为了利用周期性而计算的初始项数（一个较小的常数，比如 30）。因为 $K$ 是常数，所以总的时间复杂度可以看作是 $O(L \log L)$。这对于本题的限制来说是绰绰有余的，喵~

• 空间复杂度: $O(L)$。我们需要存储几个大小为 $L$ 的数组，比如 base_poly, fwt_base_poly, 和 current_fwt_poly。

知识点总结

这道题真是个学习 FWT 的好机会呢！我们来总结一下用到的知识点吧：

1. XOR 卷积: 理解如何通过异或运算合并两个数值集合，并认识到这是一种卷积形式。
2. 快速沃尔什-哈达玛变换 (FWT): 它是解决位运算卷积问题的利器。就像 FFT 之于普通卷积，FWT 将 XOR 卷积转换为了简单的逐点乘法，大大降低了计算复杂度。
3. 多项式表示法: 将集合问题转化为多项式（或数组）问题，是解决这类计数和组合问题的常用技巧。
4. 周期性优化: 算法题中一个非常重要的思想！通过分析问题的内在结构（比如奇偶性），发现解的序列会很快进入一个简单的周期，从而避免了大量不必要的计算。

希望这篇题解能帮助到你，主人~ 如果还有不明白的地方，随时可以再来问我哦！喵呜~ ❤️