「解题报告」[ARC146C] Even XOR

APJifengc · 2022-11-22 16:18:47 · 题解

提供一种从线性代数角度去考虑的做法。

可能会有很多线性代数的名词，如果没有线性代数基础建议现在买本线性代数教材看一遍 可以看一看别的题解的做法。

我们首先考虑没有集合大小限制怎么做：也就是求任意非空子集的异或和都不等于 0 的集合数。

由任意子集异或和，我们可以想到线性基，而线性基的本质实际上就是若干个基底张成的一个线性空间。任意非空子集异或和不等于 0 就相当于这个集合与线性基的基底组成的集合是相等的。

基底需要满足的条件就是线性无关。假如现在基底的集合大小为 i，那么这些基底张成的线性空间中包含 2^i 个向量，而这些向量显然不能选，那么可以选的向量就有 2^n-2^i 个。那么如果基底集合大小为 k，选择基底的总方案数就是 \displaystyle \prod_{i=1}^k \left(2^n-2^{i-1}\right)。

注意到这时候选择的基底是有顺序的，而集合是无序的，那么我们给方案书乘一个 \frac{1}{k!} 即可。最终的答案就是 \displaystyle \sum_{i=0}^n \frac{1}{k!}\prod_{i=1}^k \left(2^n-2^{i-1}\right)。

现在我们考虑这道题：任意大小为偶数的子集的异或和不等于 0。

我们先考虑任意大小为偶数的子集有什么性质：发现任意两个偶数大小的子集的对称差也是偶数大小。那么就可以发现，大小为偶数的子集所组成的数也可以构成一个原线性空间的线性子空间。

那么我们考虑构造这个线性子空间的一组基底。一种简单的构造方式是 \{a_1 \oplus a_2, a_1 \oplus a_3, \cdots, a_1 \oplus a_n\}。不难发现这组基底可以表示出所有集合大小为偶数的数。那么我们现在问题就和没有限制的一样了，只不过 i 个数张成的线性空间的向量数变成了 2^{i-1}，而第一个数的选择没有限制。那么式子相应的改变一下即可。最终答案就是 \displaystyle \sum_{i=0}^{n+1} \frac{1}{k!}\prod_{i=1}^k f_i,f_i=\begin{cases}2^n&(i=1)\\2^n-2^{i-2}&(i>1)\end{cases}。