CF1119H Sol

· · 题解

由于这篇题解选自一篇笔记，所以记号约定（可以先往下看，遇到不明白的记号回来找）：

若 f 是一个数组或集合幂级数，则 f' 为它的 \text{FWT}，在不引起歧义的前提下 \text{IFWT} 也采用相同的记法。

若用数组的形式来表示集合幂级数，则 $f_i$ 表示其中的一项，若用 $\sum ax^b$ 的形式表示集合幂级数，则 $[x^i]\sum ax^b$ 表示其中的一项。 $f\circ g$ 表示两个数组做卷积，本文是异或卷积，$f\cdot g$ 表示两个数组做内积，即对应位置相乘。 $c_{x,y}$ 表示 $x$ 和 $y$ 的异或**位矩阵系数**，其满足 $c(a,c)c(b,c)=c(a\oplus b,c)$，$c(a,b)=(-1)^{a\odot b}$，如果不知道什么是位矩阵请参考 [cmd 的这篇 blog](https://www.luogu.com.cn/blog/command-block/wei-yun-suan-juan-ji-yu-ji-kuo-zhan)。 下面这个性质将会用到： $$c_{i,\bigoplus_{j}b_j}=(-1)^{i\odot \bigoplus_{j}b_j}=(-1)^{\bigoplus _ji\odot b_j}=\prod_j(-1)^{i\odot b_j}=\prod_j c_{i,b_j}$$

出题人，猛。

给定 n 个可重集和 x,y,z,a_i,b_i,c_i，每个可重集可以用 (a,b,c) 描述，表示这个可重集里有 x 个 a，y 个 b，z 个 c，求在每个数组里选一个数使得它们 \oplus 和为 t 的方案数，对每个 t< 2^k 求出以上值。

考虑暴力设状态 f_{i,S} 表示考虑了前 i 个数组异或出了 S 的方案数，转移就是 f_{i,S}\gets \sum_{T\oplus a_i=S}f_{i-1,S}g_{i,T}，其中 g_{i,[a_i,b_i,c_i]}=[x,y,z]。

考虑写成异或卷积的形式，则最终结果就是 \prod(\circ)_ig_i。（\prod(\circ) 表示以 \circ 为乘法的连乘。）

也就是我们要求 \left(\prod(\cdot)g'_i\right)'。

回顾我们的位矩阵理论（我猜你们一定分得清位矩阵数组 c_{i,j} 和原题的数组 c_i），g_i 最大的特点就是有效值少，我们把它拆开（第一维不参与 \text{FWT}）：

\begin{aligned}g_{i,j}'&=\sum_kg_{i,k}c_{k,j}\\&=xc_{a_i,j}+yc_{b_i,j}+zc_{c_i,j}\\&=x(-1)^{a_i\odot j}+y(-1)^{b_i\odot j}+z(-1)^{c_i\odot j}\end{aligned}

（最后一步运用了 \oplus 位矩阵中的知识。）

然后你就发现 g_{i,j}' 一共只有 2^3=8 种可能的取值，那你如果能分别求出这些取值的系数，不就可以直接快速幂做了吗。

那我们现在就是要求类似于 p_{j,u,v,w}=\sum_i[a_i\odot j= u][b_i\odot j= v][c_i\odot j= z]。

之后由于 3 这个数很小，存在讨论解方程的做法，但我想介绍更本质的可拓展的一种做法。

我们考虑拓展原题的限制，得到更普遍的解法，将题面改成这样：

给定 n 个可重集和 w_j,a_{i,j}(i\in[1,n],j\in[0,m))，表示第 i 个可重集里有 w_{j} 个 a_{i,j}，求在每个数组里选一个数使得它们 \oplus 和为 t 的方案数，对每个 t< 2^k 求出以上值。

看到上面的最后一步，那我们现在要求的就是 p_{T,S}=\sum_i\prod_j[a_{i,j}\odot T=S_j]（S_i=0/1 则 w_i 系数为 1/(-1)），其意义为“以 S 为 1/(-1) 系数合成的数对 (\prod(\cdot)g'_i)_T 贡献了几次方”。

大体可以看出 T 是一个最外层的变量，不能动什么手脚，那我们就考虑先固定这个 T，看怎么快速求解 2^m 个 S 对应的 p_{T,S}。

如果固定 T 的话，那 p_{T,S} 就相当于具有 S 这种特质的可重集的个数，可重集就是 a_{i,j} 中的 i 这一维，这对于理解后文有帮助。

求解这 2^m 个未知数自然需要 2^m 个线性无关的方程，这引导我们把 A\subseteq[0,m)\cap\mathbb N 的 2^m 个取值变到一个幂级数 h_A=\sum_ix^{\bigoplus_{j\in A}a_{i,j}}，求解 h_A 对应的 \text{FWT} 数组 h'_A，考虑：

\begin{aligned}h_A'&=\left(\sum_ix^{\bigoplus_{j\in A}a_{i,j}}\right)'=\sum_i\left(x^{\bigoplus_{j\in A}a_{i,j}}\right)'\\ [x^T]h'_A&=\sum_ic\left(\mathop\oplus\limits_{j\in A}a_{i,j},T\right)=\sum_i\prod_{j\in A}(-1)^{a_{i,j}\odot T}\end{aligned}

最后一步的推导过程在 \oplus 位矩阵部分。

你考虑能不能把 [x^T]h'_A=\sum_i\prod_{j\in A}(-1)^{a_{i,j}\odot T} 和 p_{T,S}=\sum_i\prod_j[a_{i,j}\odot T=S_j] 建立什么对应关系，这样就可以有方程了。

（其实他俩长得挺像的。）

前文说过，p_{T,S} 指的是具有 S 这种特质的可重集的个数（i 的个数），你考虑如果 S\odot A=0（偶数个 j 在 A 中起了作用），即有偶数个 1 在 -1 的指数上产生了贡献，那这 p_{T,S} 个数对 [x^T]h'_A 的贡献就是 (-1)^{2n}=1，同理如果 S\odot A=1，则 p_{T,S} 个数对 [x^T]h'_A 的贡献系数是 -1。

即：

[x^T]h'_A=\sum_i\prod_{j\in A}(-1)^{a_{i,j}\odot T}=\sum_S(-1)^{S\odot A}p_{T,S}

这个关系就很明确了，你发现右边就是 [x^A]\left(\sum_S p_{T,S}x^{S}\right)'，所以你令 s_A=[x^T]h_A'，再给 s 求个 \text{IFWT}，你就得到了 p_{T,S}，这个过程写成代码就是 h_{A,T}\to h'_{A,T}\to p'_{T,A}\to p_{T,A} 即 p=\left((h')^T\right)'，形如一个 \text{FWT}\ - 转置 -\ \text{IFWT}，就挺神奇的。

（本来的解方程是高消三方，但是你发现关系就是 \text{IFWT}，所以直接 2^mm 搞定。）

梳理：

复杂度 \Theta(n2^m+(m+k)2^{m+k})。

代码。