题意：给定 $n$ 个数 $a_i$，每个数小于 $2 ^ m$，问对于每个 $i\in [0, m]$ 求出任意选出一些数使得异或和 __builtin_popcount 为 $i$ 的方案数。$n\leq 2\times 10 ^ 5$，$m\leq 53$。
容易发现建出线性基过后相当于是对线性基求剩下的问题。假设线性基大小为 $k$。
暴力是好做的，直接 $O(2 ^ k)$ 枚举即可，不多赘述。
对于 $k$ 比较大的，首先我们有一个暴力 DP 思路：由于线性基的性质，每一个数恰好对应一位，我们可以通过消元使得只剩每一个数只有他自己该位是 1。那么剩下的 $m - k$ 位可以直接 DP，记 $f(i, s)$ 表示选了 $i$ 个数，剩下 $m - k$ 状态为 $s$ 的方案数。于是可以做到 $O(2 ^ {m - k} m ^ 2)$，还是不够优秀。
容易发现 $m\leq 53$ 要求我们有 $O(2 ^ k)$ 和 $O(2 ^ {m - k})$ 两种做法，所以我们尝试寻找另外的方案。
考虑使用集合幂级数，令 $F_c(x) = \sum_i [|i| = c]x ^ i$，$|s|$ 表示 __builtin_popcount。将所有线性基能生成的数塞到一个集合幂级数，令为 $A$，那么 $c$ 的答案就是 $(A \times F_c)[x ^ 0]$。
考虑首先对 $A$ 做 FWT。写一个暴力可以观察到这样几个性质：
- $\text{FWT}(A)$ 只有 $2 ^ k$ 和 0 两种取值。假设当前位置为 $x$，我们考虑从线性基中任选数，如果存在一个满足 $|x \cap a_i|$ 为奇数的话，那么选他和不选他的贡献就是相反的，所以最后就是 0。否则就是 $2 ^ k$。
- 假设非 0 位置构成集合为 $B$，$B$ 是一个线性基的张集并且线性基大小为 $m - k$。容易发现对于任意一个 $a_i$，$|x\cap a_i| + |y\cap a_i|$ 和 $|(x\oplus y) \cap a_i|$ 奇偶性相同。那么说明任意 $x, y\in B$ 都有 $x\oplus y\in B$，也就说明 $B$ 是线性基张集。大小我们可以考虑由于 $2 ^ k B = \text{FWT(A)}$，我们对两边同时 iFWT 可以得到 $2 ^ k \text{iFWT}(B) = A$。观察 $A$ 包含 0，所以 $2 ^ {k - m} |B| = 1$，也就是 $|B| = 2 ^ {m - k}$。
- $B$ 线性基关键位是 $A$ 中非关键位，并且把 $A, B$ 写在一个 01 矩阵 $M$ 上满足 $i$ 行的第 $i$ 位为 1。可以证明 $M = M ^ T$。不会证，可以观察一下（
那么我们找到 $B$ 就相当是找到了 $\text{FWT}(A)$，我们把线性基翻转一下就可以得到了 $B$ 的线性基。
下面考虑如何求出 $\text{FWT}(F_c)$。容易发现最后每一个位置的答案只和 __builtin_popcount 有关。考虑 $c$ 向一个 $i\in [0, m]$ 的贡献权值，容易发现可以枚举相交部分为 $j$，那么贡献为 $(-1) ^ j \binom{i}{j} \binom {m - i}{c - j}$。直接计算是 $O(m ^ 3)$ 的，可以接受。
最后我们合并的时候还是发现最后答案只和 B 所有数的 __builtin_popcount 有关，求出张集过后直接贡献到对应位置即可。后面求 0 项值就是求所有和。注意要 iFWT 要除以 $2 ^ m$。但是线性基只有 $k$ 大小，原来是 $n$ 大小，乘上一个 $2 ^ {n - k}$ 即可。所以可以做到 $O(2 ^ {m - k})$。
平衡一下可以得到 $O(2 ^ {\frac m2} + m ^ 3)$，可以通过。
1 | void dfs(int pos, LL cur) |