practice link

题目大意：给你 $n$ 个 $m$ 位整数，对于 $\forall i,0\le i\le m$，统计 $2^{n}$ 个子集的异或和中 bitcnt 为 $i$ 的数量。

题解：考虑这 $n$ 个整数的一组基 $A$。定义 $S(A)$ 表示 $A$ 的所有子集异或和组成的集合。$\forall s\in S(A)$，以及 $A$ 以外的任意子集，$A$ 中可以恰选出一个子集使得异或和为 $s$。因此只需考虑 $A$ 中每个子集的答案，乘上 $2^{n-|A|}$ 即可。

设 $|A|=k$，若 $k\le\frac{m}{2}$，可以直接 $2^{k}$ 枚举答案。

否则，可以注意到 $A$ 中大部分位置是主元，即只有一个地方有，那么记录一下主元的数量以及非主元的状态，可得一个 $\mathcal{O}(k^{2}2^{m-k})$ 的 dp。

考虑进一步优化，将 $A$ 变换到维数较小的空间中，即可暴力计算答案再转换回来。

将 $A$ 看做一个 $2^{m}$ 维向量，$A_{i}=1\text{ iff }i\in S(A)$。对于 $\forall i,0\le i\le m$，定义 $P_{i}$ 为一个 $2^{m}$ 维向量，$P_{ij}=1\text{ iff }\text{bitcnt}(j)=i$。那么 $\text{ans}_{i}$ 即为 $A$ 和 $P_{i}$ 的异或卷积的第 $0$ 项（我真的不知道要怎么想到）。考虑 Walsh-Hadamard 变换，记变换为 $f$。答案是 $f(A)$ 和 $f(P_{i})$ 的内积除以 $2^{m}$。接下来需要研究 $f(A)$ 的性质。

由于线性基的性质，有 $A*A=A*2^{k}$，即 $f(A)*f(A)=f(A)*2^{k}$。解方程可得 $f(A)$ 的每一位必然是 $0$ 或 $2^{k}$。

$f(A)_{i}=2^{k}\text{ iff }\forall s\in S(A),2\mid\text{bitcnt}(i\land s)$。这比较显然，考虑 $f$ 的过程，每个 $s$ 位置会给 $i$ 位置贡献 $1$ 或 $-1$，而只有全部贡献 $1$ 才能得到 $2^{k}$。若 $2\mid\text{bitcnt}(i\land s)$，$2\mid\text{bitcnt}(j\land s)$，可得 $2\mid\text{bitcnt}((i\oplus j)\land s)$。因此所有这样的 $i$ 组成了一个线性空间，称为 $S(B)$。同时注意到，只需对 $A$ 中的 $s$ 满足要求即可。

$\dim S(B)=m-k$。考虑 $A^{2}_{0}$，从组合意义上来说，它等于选取 $A$ 中两组基，异或和相等的方案数，为 $2^{k}$。从 $f^{-1}(f^{2}(A))$ 的意义上来说，它等于 $\frac{2^{2k+|B|}}{2^{m}}$。因此 $|B|=2^{m-k}$。

由以上可以推出：$S(A)\oplus S(B)=F_{2}^{m}$（由定义知 $A$ 与 $B$ 正交）。那么不妨在消元时，使得 $B$ 的主元都是 $A$ 的非主元。

这时，可以发现 $A,B$ 有很奇妙的性质。对于 $B$ 的第 $j$ 个主元，如果 $A_{ij}=1$，那么 $B{ji}$ 必须等于 $1$。也就是将 $A,B$ 拼起来是个对称方阵。这样可以很容易地求出 $B$。知道 $B$ 后，就可以线性地求出 $S(B)$。

再考虑 $f(P_{i})$，由于 $P_{ij}$ 只与 $\text{bitcnt}(j)$ 有关，考虑 $f$ 的过程，$f(P_{i})_{j}$ 也只与 $\text{bitcnt}(j)$ 有关。这里组合数随便算一下即可。

时间复杂度 $\mathcal{O}(2^{m-k}+m^{3})$。