题目描述
给定 $n$ 个数字 ${a_n}$，求从中选出两个不相交的子集，使得它们不同时非空，且它们的异或和为 $0$
求方案数，其中 $1 \le n \le 10^6, 0 \le a_i \le 10^6$
题解
这篇题解可能有一些错误，忽略了吧……
相当于求有多少个非空子集使得异或和为 $0$，并将它们划分成两个集合的方案数
设 $f_{i,j}$ 表示考虑完了前 $i$ 个元素，异或和为 $j$ 的划分方案数，则：
$$
f_{i,j}=f_{i-1,j}+2f_{i-1,j \oplus a_i}
$$
设：
$$
\begin{cases}
b_{i,0}=1 \\
b_{i,a_i}=2
\end{cases}
$$
特别的，如果 $a_i=0$，则只有 $b_{i,0}=3$
那么对所有的 $b_i$ 进行异或卷积就是答案了
考虑优化，把所有的 $b_i$ 进行 $fwt$ 后再对应位置求乘积，然后再 $ifwt$ 回去就相当于进行了异或卷积
然而这个复杂度还是十分爆炸，考虑异或卷积的本质
考虑序列 $a,b$，现在要求它的异或卷积 $c$，满足：
$$
c_{k}=\sum_{i \oplus j=k}a_ib_j
$$
设某变换 $F: a \to a’$ 将序列 $a$ 映射到了序列 $a’$，使得：
$$
\begin{cases}
F(a) + F(b) = F(a + b) \\
F(a) \cdot F(b)=F(a \times b)
\end{cases}
$$
其中 $\times$ 表示卷积，且 $\cdot $ 表示点积
那么相当于要构造矩阵 ${f_{n-1,n-1}}$，有：
$$
a’ _ i=\sum _ {j=0}^{n-1}a _ jf _ {i,j}
$$
相当于这样的矩阵乘法：
$$
\begin{pmatrix}
f _ {0,0} & f _ {0,1} & f _ {0,2} & \cdots & f _ {0,n-1} \\
f _ {1,0} & f _ {1,1} & f _ {1,2} & \cdots & f _ {1,n-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
f _ {n-1,0} & f _ {n-1,1} & f _ {n-1,2} & \cdots & f _ {n-1,n-1}
\end{pmatrix}
\begin{pmatrix}
a _ {0} \\
a _ {1} \\
\vdots \\
a _ {n-1} \\
\end{pmatrix}
=
\begin{pmatrix}
a’ _ {0} \\
a’ _ {1} \\
\vdots \\
a’ _ {n-1} \\
\end{pmatrix}
$$
那么加法操作就满足了，设 $c=a+b$，则：
$$
\begin{aligned}
c’i
=&\sum _ {j=0}^{n-1} c _ j f _ {i,j} \\
=&\sum _ {j=0}^{n-1}\left( a _ j+b _ j \right)f _ {i,j} \\
=&\left( \sum _ {j=0}^{n-1}a _ jf _ {i,j} \right) + \left( \sum{j=0}^{n-1}b _ jf _ {i,j} \right) \\
=&a _ i’+b _ i’
\end{aligned}
$$
对于卷积，设 $c=a \times b$，则有：
$$
\begin{aligned}
c_i’
=&\sum_{j=0}^{n-1}c_jf_{i,j} \\
=&\sum_{j=0}^{n-1}\sum_{k \oplus w=j}a_kb_wf_{i,j} \\
\end{aligned}
$$
同时有：
$$
\begin{aligned}
c_i’
=&a_i’ \cdot b_i’ \\
=&\left( \sum_{j=0}^{n-1}a_jf_{i,j} \right) \cdot \left( \sum_{j=0}^{n-1}b_jf_{i,j} \right) \\
=&\sum_{j=0}^{n-1} \sum_{k \oplus w=j} a_kb_wf_{i,k}f_{i,w}
\end{aligned}
$$
那么 ${f_{n-1,n-1}}$ 需要满足：
$$
f_{i,k}f_{i,w}=f_{i,k \oplus w}
$$
好像叫做卷积定理
由于某种原因，在满足交换律、结合律、循环律的 $k$ 进制卷积中，设权值 $i$ 的最小循环节为 $\tau_i$，即最小的非 $0$ 的 $j$，满足 $i^j=1$，设这个 $j$ 为 $\tau_i$
那么有：
$$
f_{i,j}=\omega_{\tau_{i}}^{\lambda_{i,j}}
$$
于是只需要构造：
$$
\lambda _ {k} + \lambda _ {w}=\lambda_{k \oplus w}
$$
只会爆搜
当然由于需要逆变换，也就是存在逆矩阵，那么需要保证 $f_0 \sim f_{n-1}$ 线性无关
好像扯远了……对于异或卷积，有：
$$
f_{i,j}=(-1)^{\text{popcount}(i \cap j)}
$$
即：
$$
a’ _ i=\sum_{j=0}^{n-1}a _ j(-1)^{\text{popcount}(i \cap j)}
$$
若 $a_0=3$，则只有 $a_0$ 会产生贡献，即：
$$
a_i’=a_0(-1)^{\text{popcount}(i \cap 0)}=3
$$
若 $a_0=1,a_x=2$，则：
$$
\begin{aligned}
a_i’
=&a_0(-1)^{\text{popcount}(i \cap 0)}+a_x(-1)^{\text{popcount}(i \cap x)} \\
=&1+2(-1)^{\text{popcount}(i \cap x)} \\
=&3[2|\text{popcount}(i \cap x)]+(-1)[2 \not | \text{popcount}(i \cap x)]
\end{aligned}
$$
也就是说 $a_i’ \in \{-1,3\}$
由于把所有的 $a$ 加起来进行 $fwt$ 等于分别进行 $fwt$ 后加起来，不妨采用前者
那么假设 $a’_i$ 有 $x$ 个 $-1$，有 $n-x$ 个 $3$，则：
$$
3(n-x)-x=a_i’
$$
可以得到：
$$
x=\frac{3n-a_i’}{4}
$$
也就是在 $i$ 这一维，有 $x$ 个 $-1$ 和 $n-x$ 个 $3$
那么对于这一位进行分别 $fwt$ 后再求乘积的结果就是 $(-1)^x3^{n-x}$
于是就做完了
