ARC146C

· · 题解

发现很多人都在发这题题解，那么我来复读一下 APJ 做法凑个热闹 .

APJifengc 第一小定理：

满足其所有非空子集的异或和不为 0 的集合 S\subseteq\{0,1,2,3,\cdots,2^n-1\} 的数量为

\sum_{i=0}^n\dfrac1{i!}\prod_{j=1}^i(2^n-2^{j-1})

证明：见 各种小定理 .

这样就解决了没有奇数限制的问题 .

有限制的也差不多，注意到如果两个大小为奇数的集合 A,B 异或和相等，则 A\oplus B 是一个大小为偶数的异或和为 0 的集合，不符题意，于是所有大小为奇数的集合异或和均不同 .

于是根据 APJifengc 第一小定理的类似推导即可得到答案就是

\sum_{i=0}^n\dfrac1{i!}\prod_{j=1}^i(2^n-2^{j-2})

corner case 省略 .

APJ 的另一个推法是考虑对于序列 \{a\} 构造基底 a_1\oplus a_2,a_1\oplus a_3,a_1\oplus a_4,\cdots，这样显然是一组合法解 .

于是第 i 步的时候有 i-1 个数，也就有 i-2 个基底，这样就表明把 APJifengc 第一小定理的 2^n-2^{j-1} 改成 2^n-2^{j-2} 即可，完整式子同上 .

Classical 做法见 Official Editorial .