题目描述

给定 $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}$

于是就做完了