集合变换学习笔记

总结一下有关子集变换的笔记。

约定：

1. 接下来我们讨论的序列一般指长度为$2^n$，下标从$0$开始的序列。例如$a_0, a_1, \ldots, a_{2^n-1}$。
2. 集合幂级数其实可以理解为以集合为下标的序列。本质上就是普通的序列，只不过是用集合的运算表示位运算。本文中的序列可能指集合幂级数，也可能指普通序列，具体见上下文或者使用的记号。
3. 集合占位多项式可以理解为是一个序列，序列中的每个元素都是一个多项式。

快速莫比乌斯变换

子集与

考虑形式化的问题：对于两个序列$a,b$，我们希望求序列$c$：

$$c_i=\sum_{j\& k=i} a_j b_k$$

用集合幂级数的语言，我们想求的是

$$c_S=\sum_{S=P\cap Q} a_P b_Q$$

其中$S$是集合。接下来的问题与过程形式都使用集合来展现。

考虑做一个高维后缀和的变换。对于集合幂级数$f$定义$f'$：

$$f'_S=\sum_{S\subseteq T}f_T$$

那么我们对$a$和$b$同时做高维后缀和变换得到：

$$\begin{aligned} c'_S&=\sum_{S\subseteq T}c_T=\sum_{S\subseteq P\cap Q}a_P b_Q\\ &=\sum_{S\subseteq P}a_P\sum_{S\subseteq Q}b_Q\\ &=a'_Sb'_S \end{aligned}$$

也就是说如果我们能快速计算$a$和$b$的高维后缀和，就可以快速得到$c$的高维后缀和$c'$。

在求出了$c'$后，我们希望还原成$c$，可以用容斥得到

$$c(T)=\sum_{T\subseteq S}(-1)^{|T|-|S|}c'(S)$$

但其实没必要这么麻烦。我们可以直接倒着写高维后缀和，就可以逆变换回去。

高维后缀和可以写成

for(int i=0;i<n;i++){
    for(int j=0;j<(1<<n);j++)
        if((j&(1<<i))==0)
            s[j]+=s[j+(1<<i)];
}

高维后缀差分（逆变换）：

for(int i=0;i<n;i++){
    for(int j=0;j<(1<<n);j++)
        if((j&(1<<i))==0)
            s[j]-=s[j+(1<<i)];
}

时间复杂度$O(n2^n)$，空间复杂度$O(2^n)$。

子集或

对于序列$a,b$，我们想求

$$c_S=\sum_{S=P\cup Q}a_Pb_Q$$

类似的，我们这次定义一个高维前缀和：

$$f'_S=\sum_{T\subseteq S}f_S$$

则可以推出

$$\begin{aligned} c'_S&=\sum_{T\subseteq S}c_T=\sum_{P\cup Q\subseteq S}a_Pb_Q\\ &=\sum_{P\subseteq S}a_P\sum_{Q\subseteq S}b_Q\\ &=a'_Sb'_S \end{aligned}$$

于是类似地使用高维前缀和与高维前缀差分即可。

扩域情况

对于集合幂级数而言，每一个元素只有选或者不选两种情况。换言之，二进制数的每个位只有$0$或者$1$两种值。而对于可重集，即$k$进制数来说，也是可以定义集合幂级数以及高维前（后）缀变换的。

以子集与为例，高维后缀和变换可以一般地表示为

$$c(\min(a_1,b_1),\min(a_2,b_2),\cdots,\min(a_n,b_n)) =\sum a(a_1,a_2,\cdots,a_n)b(b_1,b_2,\cdots,b_n)\\ c'(p_1,p_2,\cdots,p_n)=\sum_{p_i\le q_i}c(q_1,q_2,\cdots,q_n)$$

取$\min$相当于与运算；$p_i\le q_i$相当于后缀和操作。

分治多项式乘法

为了理解 FWT 的 xor 变换在干啥，我们先引入分治多项式乘法。

我们有两个定义在加法乘法环下的$n-1$次多项式$A,B$，我们想求$A(x)B(x)$。设

$$\begin{aligned} A(x) &= P_1(x)x^{n/2}+P_2(x)\\ B(x) &= Q_1(x)x^{n/2}+Q_2(x) \end{aligned}$$

假定$n$是$2$的幂。则我们有

$$\begin{aligned} A(x)B(x) &= (P_1(x)x^{n/2}+P_2(x))(Q_1(x)x^{n/2}+Q_2(x))\\ &= (P_1Q_1)x^n+(P_1Q_2+P_2Q_1)x^{n/2}+P_2Q_2\\ \end{aligned}$$

而我们知道

$$P_1Q_2+P_2Q_1=(P_1+Q_1)(P_2+Q_2)-P_1Q_1-P_2Q_2\\$$

因此可以只算$P_1Q_1,P_2Q_2,(P_1+Q_1)(P_2+Q_2)$的乘法，递归下去。时间复杂度

$$T(n)=3T(n/2)+O(n)=O(n^{\log_23})\\$$

异或卷积

异或卷积问题：对于序列$a,b$，我们要求

$$c_i=\sum_{j\oplus k=i}a_jb_k$$

$\oplus$表示位异或运算。

我们首先介绍分治异或卷积算法，然后介绍广泛使用的快速沃尔什变换。了解分治异或卷积算法有利于理解快速沃尔什变换。

分治异或卷积

由于异或具有结合律、交换律，对加法的分配律，则我们定义一个指数通过异或运算合并的多项式来表示该序列：

$$C(x)=\sum_{i = 0}^{2^n-1} c_ix^i$$

可以理解为是“异或生成函数”。类似地我们定义出$A(x) = \sum_i a_i x^i$以及$B(x) = \sum_i b_i x^i$，那么有$C(x) = A(x) B(x)$。这里的乘法定义为

$$A(x) B(x) = \sum_{i = 0} ^ {2^n-1} \sum_{j = 0} ^ {2^n-1}a_i b_j x^{i\oplus j}$$

为了计算上述异或乘法，我们将多项式前后拆成两半。设

$$\begin{aligned} A(x) &= P_1x^{2^{n-1} }+ P_2\\ B(x) &= Q_1x^{2^{n-1} }+ Q_2 \end{aligned}$$

则使用分治可以得到

$$\begin{aligned} C(x) &= A(x) B(x)\\ &= (P_1x^{2^{n-1} }+ P_2) (Q_1x^{2^{n-1} }+ Q_2)\\ &= P_1Q_1 + (P_2Q_1 + P_1Q_2)x^{2^{n-1} } + P_2Q_2 x^{2^{n-1} \oplus 2^{n-1} } \\ &= P_1Q_1 + (P_2Q_1 + P_1Q_2)x^{2^{n-1} } + P_2Q_2 \\ &= (P_1Q_1 + P_2Q_2) + (P_2Q_1 + P_1Q_2)x^{2^{n-1} } \end{aligned}$$

这里有个特殊之处：由于下标的异或运算使得$P_2 Q_2$项的指数被消掉了，因此我们实际上只用递归算两次多项式乘法。我们设

$$X=(P_1+P_2)(Q_1+Q_2)\\ Y=(P_1-P_2)(Q_1-Q_2)$$

于是可以得到

$$\begin{aligned} P_1Q_1+P_2Q_2 &= \frac{X+Y}{2} \\ P_2Q_1+P_1Q_2 &= \frac{X-Y}{2} \end{aligned}$$

那么$C(x) = \frac{X + Y}{2} + \frac{X - Y}{2}x^{2^{n-1} }$。

时间复杂度就是

$$T(2^{n-1} )=2T(2^{n-1} )+O(2^n)=O(n2^n)\\$$

事实上，与卷积和或卷积也可以使用分治多项式乘法去理解。

快速沃尔什变换

快速沃尔什变换（Fast Walsh–Hadamard transform，FWT or FWHT）¹是用于快速计算一个序列的沃尔什变换的算法。在算法竞赛领域中，大多数时候 FWT 的作用是快速计算异或卷积。

FWT 的本质是把$a$变成了

$$\text{FWT}(a)_i=\sum_j a_j (-1)^{\operatorname{popcount}(i\& j)}$$

写成集合幂级数的形式就是

$$\text{FWT}(a)(S)=\sum_{T}a(T) (-1)^{|S\cap T|}$$

不过直接抛出 FWT 的定义并不能帮助我们理解为什么 FWT 可以加速异或卷积的计算。

通过分治异或卷积理解

为此我们沿用上文中分治异或卷积的描述。

首先我们要更改分治异或卷积的执行顺序，更准确地说是拆分。

分治异或卷积的优化用一句话概括就是：将计算$(P_1x^{2^{n-1} }+ P_2)(Q_1x^{2^{n-1} }+ Q_2)$归约到计算$(P_1+P_2)(Q_1+Q_2)$和$(P_1-P_2)(Q_1-Q_2)$两个长度减半的异或卷积。

在实现的时候设$\text{Solve}(l, r)$表示将$\sum_{i = l} ^ r a_i x^i$与$\sum_{i = l} ^ r b_i x^i$做异或卷积。

我们不妨考虑将$A(x) = (P_1x^{2^{n-1} }+ P_2)$变成$A'(x) = ((P_1 - P_2)x^{2^{n-1} } + (P_1 + P_2))$，将$B(x) = (Q_1x^{2^{n-1} }+ Q_2)$变成$B'(x) = ((Q_1 - Q_2)x^{2^{n-1} } + (Q_1 + Q_2))$。对于这两个新的多项式：

• 首先我们将其前半部分做卷积，后半部分做卷积，即递归调用$\text{Solve}(l, mid)$和$\text{Solve}(mid+1, r)$。
• 经过上一步我们计算出了$X$和$Y$，然后再根据$C(x) = \frac{X + Y}{2} + \frac{X - Y}{2}x^{2^{n-1} }$，还原出$C$的系数表示即可。

考虑第一步和第二步本质上做了什么事情。他们其实执行的计算是差不多的，只不过第二步需要除以$2$而第一步不需要。且第一步我们需要同时变换$A$和$B$，而在第二步里$X$和$Y$其实表示的是同一个多项式的高低位。

因此我们有一个想法：我们将第一步的过程和第二步的过程拆开，再将第一步中对$A$和$B$的变换过程拆开！

换言之我们的操作过程变成：

• 先分别递归变换$A$和$B$得到$\mathcal{T}(A)$和$\mathcal{T}(B)$。
• 这时$\mathcal{T}(A)$和$\mathcal{T}(B)$里存的分别是$2^n$个单项式（只有常数项的多项式）。因此我们直接将两者点乘得到$\mathcal{T}(C)$。
• 然后递归地自底向上执行第二步的过程，将$\mathcal{T}(C)$转化为最后的$C$。

由于这三个过程彼此不相关，只要顺序不要乱就行，因此拆开的正确性有保证。

接下来我们要理解对$A$的变换是 FWT 变换。

以$A$为例，我们分析对$A$的变换：将$A(x) = (P_1x^{2^{n-1} }+ P_2)$变成$A'(x) = ((P_1 - P_2)x^{2^{n-1} } + (P_1 + P_2))$，然后前后两半递归变换。

设$\mathcal{T}(A) = \sum_{i = 0} ^ {2^n-1} t_i x^i$，那么我们对于$i$分析$t_i$的值是如何得到的。

以$n=3, 2^n=8$的情况为例，我们用绿色线表示系数为正，红色线表示系数为负，画出从$A$变换为$\mathcal{T}(A)$的示意图：

考虑$a_j$对$t_i$的贡献。那么我们只需要考虑$a_j$对$t_i$贡献的系数是$1$还是$-1$即可，这显然由从$a_j$到$t_i$路径上的红色箭头数量的奇偶性决定。为此我们枚举考虑$i$和$j$二进制下第$k$位：

• 如果两者第$k$位是相同的，那么走的就是水平方向的，这时是否为红色箭头取决于这一位是否为$1$；
• 如果两者第$k$位不同，那么$j$得走斜着的箭头，而斜着的箭头是不存在红色的。

综上所述，系数即为$(-1)^{\text{popcount}(i\&j)}$。因此$t_i = \sum_{j = 0} ^ {2^n - 1} a_j (-1)^{\text{popcount}(i\&j)}$，这恰好就是 FWT 变换的定义。

代码实现

FWT 和 IFWT 的递归过程为

$$\begin{array}{r|l|r|l} \hline 1 & \textbf{function }\text{FWT}(a,l,r)& 1 & \textbf{function }\text{IFWT}(a,l,r)\\ 2 & \qquad m \gets \frac{r-l}{2}& 2 & \qquad \text{IFWT}(a,l,l+m)\\ 3 & \qquad \textbf{for }i=l\textbf{ to }l+m-1& 3 & \qquad \text{IFWT}(a,l+m,r)\\ 4 & \qquad \qquad x \gets a_i& 4 & \qquad m \gets \frac{r-l}{2}\\ 5 & \qquad \qquad y \gets a_{i+m}& 5 & \qquad \textbf{for }i=l\textbf{ to }l+m-1\\ 6 & \qquad \qquad a_i \gets x+y& 6 & \qquad \qquad x \gets a_i\\ 7 & \qquad \qquad a_{i+m} \gets x-y& 7 & \qquad \qquad y \gets a_{i+m}\\ 8 & \qquad \textbf{end for} & 8 & \qquad \qquad a_i \gets \frac{x+y}{2}\\ 9 & \qquad \text{FWT}(a,l,l+m)& 9 & \qquad \qquad a_{i+m} \gets \frac{x-y}{2}\\ 10 & \qquad \text{FWT}(a,l+m,r)& 10 & \qquad \textbf{end for} \\ 11 & \textbf{end function} & 11 & \textbf{end function} \\ \hline \end{array}$$

异或卷积则是 FWT 后直接做乘法：$\operatorname{IFWT}( \operatorname{FWT}(a) \times \operatorname{FWT}(b) )$。

事实上，$\operatorname{IFWT}(a) = \operatorname{FWT}(a)\cdot 2^{-n}$。因此非递归版本的 IFWT 也可以直接在最后除掉一个$2^n$。

模板代码

Trick

有一个小 Trick 就是，如果我们修改$\operatorname{FWT}(a)(0)$，那么等$\operatorname{IFWT}$变换回去后，所有项都被增加一个常量（这个常量不一定等于我们修改的差量）。原因如上所述，$a_0$的贡献永远是正的。

这个性质可以用来解一些要求$a_0=0$的题，那么我们给$\operatorname{FWT}(a)(0)$随机一个值，变换回去后把所有项都减掉$a_0$即可。

子集卷积

我们考虑这样一个问题：求不相交的或卷积：

$$c_S=\sum_{P\cup Q=S,P\cap Q=\varnothing}a_P b_Q$$

这个不好求。我们设一个集合占位多项式：

$$\begin{aligned} A_{S}(x) &= \sum_{T\subseteq S} a_Tx^{|T|} = \sum_{i} x^i \sum_{T\subseteq S,|T|=i} a_T \\ B_{S}(x) &= \sum_{T\subseteq S} b_Tx^{|T|} = \sum_{i} x^i \sum_{T\subseteq S,|T|=i} b_T \end{aligned}$$

左右两个定义是等价的。

令$C_S(x) = A_S(x) B_S(x)$则可以得到

$$\begin{aligned} C_S(x) &= \sum_{P\subseteq S} a_P x^{|P|} \sum_{Q\subseteq S}b_Q x^{|Q|} \\ &= \sum_{P\subseteq S} \sum_{Q\subseteq S} a_P b_Q x^{|P|+|Q|} \\ &= \sum_{P \cup Q \subseteq S} a_P b_Q x^{|P|+|Q|} \\ \end{aligned}$$

把这个逆变换得到

$$c_S = \sum _{P\cup Q = S}a_P b_Q x^{|P|+|Q|}$$

这时你会发现，当$|P| + |Q| = |S|$时有$P\cup Q=S,P\cap Q=\varnothing$。因此我们取$[x^{|S|}] c_S$就是答案。

时间复杂度为

$$2O(n2^n)+O(n^22^n)+O(n2^n)=O(n^22^n)$$

在实现的时候有一个技巧，就是在暴力卷积的时候要稍微调整循环顺序，不要一列一列访问内存，不然常数极大。

代码

HDU 5823

首先显然色数是$\le n$的，因为你每个点染不同颜色一定是成立的。

而显然每种颜色可以染一个独立集。设$f(S)$表示点集$S$是否是一个独立集，$g(S,x)$表示$S$点集能否使用$x$种颜色染。则

$$g(S,1)=f(S)\\ g(S,i)=\left[\sum_{T\subseteq S}g(T,i-1)f(S\setminus T)\right]\\ g(P\cup Q,i)=\left[\sum_{P\cap Q=\varnothing}g(P,i-1)f(Q)\right]$$

但事实上$P\cap Q=\varnothing$不是必要条件，它不会影响最优解。因此这就是一个子集或卷积，需要做$n$次，每次卷完要回来转成艾弗森括号运算值。总复杂度$O(n^22^n)$。

代码

CF1034 E

求$c_S=\sum_{P\cup Q=S,P\cap Q=\varnothing}a_Pb_Q\bmod 4$。$n\le 21$。

可以使用上述子集卷积做法，复杂度$O(n^22^n)$，在这道题中是不能通过的。

设

$$\begin{aligned} A_S(p) &= \sum_{T\subseteq S}a_Tp^{|T|}\\ B_S(p) &= \sum_{T\subseteq S}b_Tp^{|T|} \end{aligned}$$

设$F_S(p) = A_S(p)B_S(p)$，还原一下有$f_S(p) = \sum_{P\cup Q = S}a_P b_Q p^{|P| + |Q|}$。

注意到$f_S(p)$这个多项式的最低次项的指数是$|S|$。而我们要的就是所有$[p^{|S|}]f_S$的和（即$|P| + |Q| = |S|$）。

设$p=4$，这题要求对$4$取模。

那么我们可以直接把$p=4$代入$\frac{f_S(p)}{p^{|S|}}$这个多项式，因为是对$4$取模，因此除了常数项之外的其他项的贡献都是$0$。实现的时候开 LL 暴力右移即可。

代码

HDU 5330

这道题虽然名称上是状圧 DP，但在 DP 的过程中是按维度考虑，其实是在做一个高维前缀和的过程。这样就更容易理解它 DP 的含义了。

具体的 DP 方法可以见注释。

代码

AGC034 F

设$E(x)$表示从$0$变到$x$的期望：

$$E(x)=1+\sum_{i=0}^{2^n-1}E(i)p_{x\oplus i}\\ =1+\sum_{i=0}^{2^n-1}E(x\oplus i)p_i \\$$

且$p_x=\dfrac{A_x}{S},E(0)=0$。注意到这是一个异或卷积的形式（$x\oplus i\oplus i=x$），则这个等式可以被表示为

$$\left\langle E(0),E(1),\cdots,E(2^n-1) \right\rangle \oplus \left\langle p_0,p_1,\cdots,p_{2^n-1} \right\rangle=\left\langle ?,E(1)-1,E(2)-1,\cdots,E(2^n-1)-1 \right\rangle$$

$E(0)=0$，不满足和式，因此表示为$?$状态。

由于$\sum_{i=0}^{2^n-1}p_i=1$，而在上述异或卷积中每个$E(i)$都和所有的$p_i,i\in[0,2^n-1]$乘起来贡献了一次。因此

$$E(0)+E(1)+\cdots+E(2^n-1)=?+(E(1)-1)+(E(2)-1)+\cdots +(E(2^n-1)-1)\\ ?=E(0)+2^n-1$$

于是得到

$$\left\langle E(0),E(1),\cdots,E(2^n-1) \right\rangle \oplus \left\langle p_0,p_1,\cdots,p_{2^n-1} \right\rangle\\ =\left\langle E(0)+2^n-1,E(1)-1,E(2)-1,\cdots,E(2^n-1)-1 \right\rangle$$

我们想办法把所有$E(x)$消掉：

$$\left\langle E(0),E(1),\cdots,E(2^n-1) \right\rangle \oplus \left\langle p_0-1,p_1,\cdots,p_{2^n-1} \right\rangle=A=\left\langle 2^n-1,-1,-1,\cdots,-1 \right\rangle$$

于是我们 FWT 之后计算$\operatorname{FWT}(A)(i)/\operatorname{FWT}(p)(i)$，然后再转回来即可。因为最后的答案是强制$E(0)=0$，所以在做的时候可以直接乘上逆元。最后使用 FWT 本质的 Trick 即可。

时间复杂度$O(2^nn)$。

代码

¹. https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform ↩