哈集幂入门
Brokwind
·
·
算法·理论
前言
作者水平有限,只能做一些最基本的介绍。
需要读者会写高维前缀和。
文章使用 DeepSeek 进行润色。
如果 NOIP 之后没退役的话会补充子集卷积部分的例题。
子集/超集和
把每一维当成取值为 \{0,1\} 的一维,实际上就是高维前/后缀和,枚举当前考虑了第几维进行计算即可。
例题
[USACO23FEB] Problem Setting P
很容易发现转移是一个类似枚举子集的结构,直接做是 O(3^m) 的。
发现可以对集合大小分层进行转移,那每层转移时就是对前面所有已经得出的值求子集和,这样就可以做 O(m^2 2^m)。
但这题还可以做到更好。
我们考虑转移的同时处理子集和。在计算时,我们实际会得到 m 个中间数组,表示所有前 i 位是当前集合子集,而后面与当前集合完全一致的所有集合的权值之和。维护这些中间数组,从小到大枚举当前集合,转移时可以枚举上一步的集合与当前集合最后一个不同的位,这样只需要用到已经算过的位置。算出此位置 dp 值后计算中间数组在此位置的值,很容易 O(m) 递推出来,这样就可以做到 O(m 2^m) 的复杂度。
与/或/异或卷积
思路
首先,集合幂级数跟幂级数的关系其实不大,里面的变量算是起到占位符的作用,只是说可能表示起来方便点。一般来说,一个集合幂级数 F(x)=\sum f_S x^S 可以认为它代表了一类集合的一些信息,其中集合 S 对应了 f_S 中的信息,一般用状压的方式把集合变成序列中的下标。
我们可以把 F 和 G 的卷积推广成 \sum f_S g_T x^{S\oplus T},如果 \oplus 是加法就是通常意义下的多项式乘法。对于集合幂级数来说,\oplus 一般为位运算。
现在我们思考一下如何快速计算位运算的卷积,比如或卷积,也就是把 \oplus 定义为或操作。位运算的常见处理技巧是拆位,所以我们尝试拆位去做。
我们可以模仿 FFT,构造一组变换 \mathcal{T} 和 \mathcal{T}^{-1},设 F'=\mathcal{T}(F),可以使得:
对于 H=F\ast G,h'_S=f'_S g'_S。
这样,我们求解 F 和 G 变换后的结果,对应项相乘就得到 H 变换后的结果,再用逆变换得到 H。
或卷积
如果集合只有一位的话,那么我们可以直接写出来 H 的各项系数:
h_1=f_0g_1+f_1g_0+f_1g_1,
h_0=f_0g_0.
不妨假设变换是线性变换,设变换矩阵为
A=\begin{pmatrix}a&b\\c&d\end{pmatrix},
也就是把 f 排成列向量 \begin{pmatrix}f_1\\f_0\end{pmatrix},变换写成 f'=Af,即
\begin{pmatrix}f'_1\\f'_0\end{pmatrix}
=\begin{pmatrix}a&b\\c&d\end{pmatrix}\begin{pmatrix}f_1\\f_0\end{pmatrix},
于是 f'_1=af_1+bf_0,f'_0=cf_1+df_0。那么
h'_1=b h_0+a h_1=b f_0g_0+a f_0g_1+a f_1g_0+a f_1g_1,
h'_0=d h_0+c h_1=d f_0g_0+c f_0g_1+c f_1g_0+c f_1g_1.
因为要用相同的变换,所以
\begin{aligned}
&f'_1=a f_1+b f_0,\quad f'_0=c f_1+d f_0,\\
&g'_1=a g_1+b g_0,\quad g'_0=c g_1+d g_0.
\end{aligned}
那么由于 h'_S=f'_S g'_S,我们有
\begin{aligned}
b f_0g_0+a f_0g_1+a f_1g_0+a f_1g_1
&=b^2f_0g_0+abf_0g_1+abf_1g_0+a^2f_1g_1,\\
d f_0g_0+c f_0g_1+c f_1g_0+c f_1g_1
&=d^2f_0g_0+cdf_0g_1+cdf_1g_0+c^2f_1g_1.
\end{aligned}
各项系数需完全相等,所以
\begin{aligned}
a&=a^2,\qquad b=b^2,\\
c&=c^2,\qquad d=d^2,\\
a&=ab,\qquad c=cd.
\end{aligned}
大致扫一眼发现四个数都要么是 0 要么是 1。
为了有逆变换,行列式 ad-bc 不能为 0,所以 ad 和 bc 一个是 1 一个是 0。在 a,b,c,d\in\{0,1\} 且 a=ab、c=cd 的约束下,只有两种可能:要么
a=1,\quad b=1,\quad c=0,\quad d=1,
要么
a=0,\quad b=1,\quad c=1,\quad d=1.
写成矩阵就是
A=\begin{pmatrix}1&1\\0&1\end{pmatrix}
\quad\text{或}\quad
A=\begin{pmatrix}0&1\\1&1\end{pmatrix}.
我们一般用前一个。
那么逆矩阵就是
A^{-1}=\begin{pmatrix}1&-1\\0&1\end{pmatrix}.
现在我们就可以处理集合大小为 1 的集合幂级数或卷积了,可喜可贺。
问题来了:如何处理更大的集合?
因为位运算每一位互不相干,我们可以尝试对每一位都进行这样的变换,然后按位相乘,再对每一位进行逆变换。可以发现由于变换不会跨位修改,位与位之间确实不存在干扰。
如果集合大小为 n,复杂度就是 O(n2^n)。
写成代码就是:
for(int i=0;i<n;i++) for(int j=0;j<(1<<n);j+=(1<<(i+1))) for(int k=j;k<(j|(1<<i));k++) f[k|(1<<i)]+=f[k],g[k|(1<<i)]+=g[k];
for(int i=0;i<(1<<n);i++) h[i]=f[i]*g[i];
for(int i=0;i<n;i++) for(int j=0;j<(1<<n);j+=(1<<(i+1))) for(int k=j;k<(j|(1<<i));k++) h[k|(1<<i)]-=h[k];
注意如果要复用 f 或 g 数组中值的话要补上对它们的逆变换。
与卷积
同理可以求解出与卷积的变换矩阵:
A=\begin{pmatrix}1&0\\1&1\end{pmatrix},\qquad
A^{-1}=\begin{pmatrix}1&0\\-1&1\end{pmatrix}.
异或卷积
同理也可求出异或卷积的变换矩阵:
A=\begin{pmatrix}-1&1\\1&1\end{pmatrix},\qquad
A^{-1}=\frac12\begin{pmatrix}-1&1\\1&1\end{pmatrix}.
即 f'_1=f_0-f_1,f'_0=f_0+f_1,且 A^2=2I,所以逆矩阵就是 \frac12A。
代码:
for(int i=0;i<n;i++) for(int j=0;j<(1<<n);j+=(1<<(i+1))) for(int k=j;k<(j|(1<<i));k++){
int x=f[k],y=f[k|(1<<i)];
f[k]=x+y,f[k|(1<<i)]=x-y;
x=g[k],y=g[k|(1<<i)];
g[k]=x+y,g[k|(1<<i)]=x-y;
}
for(int i=0;i<(1<<n);i++) h[i]=f[i]*g[i];
for(int i=0;i<n;i++) for(int j=0;j<(1<<n);j+=(1<<(i+1))) for(int k=j;k<(j|(1<<i));k++){
int x=h[k],y=h[k|(1<<i)];
h[k]=(x+y)/2,h[k|(1<<i)]=(x-y)/2;
}
小结
三种位运算卷积的变换矩阵分别是
\begin{pmatrix}1&1\\0&1\end{pmatrix},\qquad
\begin{pmatrix}1&0\\1&1\end{pmatrix},\qquad
\begin{pmatrix}-1&1\\1&1\end{pmatrix},
逆变换对应换成各自的逆矩阵,总复杂度都是 O(n2^n)。
例题
[USACO24DEC] All Pairs Similarity P
设集合 S 出现次数为 a_S,先推一下式子:
\begin{aligned}
ans_S&=\sum_T a_T \frac{\lvert S\cap T\rvert}{\lvert S\cup T\rvert}\\
&=\sum_T a_T \frac{\lvert S\rvert + \lvert T\rvert -\lvert S\cup T\rvert}{\lvert S\cup T\rvert}\\
&=\sum_T a_T (\frac{\lvert S\rvert}{\lvert S\cup T\rvert}+\frac{\lvert T\rvert}{\lvert S\cup T\rvert}-1)\\
&=\lvert S\rvert\sum_T \frac{a_T}{\lvert S\cup T\rvert}+\sum_T \frac{a_T \lvert T\rvert}{\lvert S\cup T\rvert}-n
\end{aligned}
比较难的是计算两个和式:
\sum_T \frac{a_T}{\lvert S\cup T\rvert}\qquad \sum_T \frac{a_T \lvert T\rvert}{\lvert S\cup T\rvert}
发现我们可以分离出 T 和 S\cup T 两个变量,问题可以变为已知 f,g 两个数列,h_S=\sum_T f_T g_{S\cup T},求 h。
这里介绍两个做法。
法一:手搓变换矩阵
注意到 g 的下标是 S\cup T,如果把 T 和 S\cup T 看成自变量,反推 S 会得到一个多值位运算 \oplus:
发现运算没有交换律,f 和 g 是可区分的,如果还是对三个数列应用同一变换能够处理的只有满足交换律的运算,所以我们需要多个变换。直接设三个矩阵,分别解出来。
还是拆位,由定义直接写出 H 的各项系数:
h_1=f_0g_1+f_1g_1,
h_0=f_0g_0+f_1g_1.
这次 f,g,h 用的不一定是同一个矩阵,设
A_f=\begin{pmatrix}a&b\\c&d\end{pmatrix},\qquad
A_g=\begin{pmatrix}e&f\\g&h\end{pmatrix},\qquad
A_h=\begin{pmatrix}p&q\\r&s\end{pmatrix}.
把向量写成列向量,变换就是
\begin{pmatrix}f'_1\\f'_0\end{pmatrix}
=\begin{pmatrix}a&b\\c&d\end{pmatrix}
\begin{pmatrix}f_1\\f_0\end{pmatrix},
即
f'_1=af_1+bf_0,\qquad f'_0=cf_1+df_0,
先展开左边:
$$
h'_1=ph_1+qh_0=qf_0g_0+pf_0g_1+(p+q)f_1g_1.
$$
右边:
$$
f'_1g'_1=(af_1+bf_0)(eg_1+fg_0)=aef_1g_1+aff_1g_0+bef_0g_1+bff_0g_0.
$$
比较 $f_0g_0,f_0g_1,f_1g_0,f_1g_1$ 的系数:
$$
\begin{cases}
q=bf,\\
p=be,\\
0=af,\\
p+q=ae.
\end{cases}
$$
同理,对 $h'_0$:
$$
h'_0=rh_1+sh_0=sf_0g_0+rf_0g_1+(r+s)f_1g_1,
$$
$$
f'_0g'_0=(cf_1+df_0)(gg_1+hg_0)=cgf_1g_1+chf_1g_0+dgf_0g_1+dhf_0g_0,
$$
得到
$$
\begin{cases}
s=dh,\\
r=dg,\\
0=ch,\\
r+s=cg.
\end{cases}
$$
解这个方程组。由 $af=0$ 取 $f=0$,由 $ch=0$ 取 $c=0$,这样两个矩阵仍然可逆。于是 $q=0$,$p=be$,代入 $p+q=ae$ 得 $e(a-b)=0$,取 $e\ne0$ 就有 $a=b$;同理 $r=dg$、$s=dh$ 代入 $r+s=cg$ 得 $d(g+h)=cg$,取 $g\ne0$。
取 $e=1$、$g=-1$、$a=d=h=1$,则 $b=1$、$c=0$,进而
$$
p=be=1,\quad q=0,\quad r=dg=-1,\quad s=dh=1.
$$
于是
$$
A_f=\begin{pmatrix}1&1\\0&1\end{pmatrix},\qquad
A_g=\begin{pmatrix}1&0\\-1&1\end{pmatrix},\qquad
A_h=\begin{pmatrix}1&0\\-1&1\end{pmatrix}.
$$
推广到 $k$ 位,对每一位都做上述变换,则 $h'_S=f'_Sg'_S$。
##### 法二:转置原理
把整个做法看成在 $g$ 上乘了一个矩阵,依然拆位:
$$
\begin{pmatrix}h_1\\h_0\end{pmatrix}
=\begin{pmatrix}f_1+f_0&0\\f_1&f_0\end{pmatrix}
\begin{pmatrix}g_1\\g_0\end{pmatrix}
$$
发现矩阵转置一下就是:
$$
\begin{pmatrix}h_1\\h_0\end{pmatrix}
=\begin{pmatrix}f_1+f_0&f_1\\0&f_0\end{pmatrix}
\begin{pmatrix}g_1\\g_0\end{pmatrix}
$$
这是或卷积对应的矩阵。
所以这个算法实际是或卷积的转置,套用转置原理把代码倒过来写一遍就行了。
转置原理这个坑有点大,等以后写多项式相关的时候再考虑展开写吧。
#### [[NOI2025] 集合](https://www.luogu.com.cn/problem/P13275)
首先我们可以尝试直接 dp。设 $f_{i,S,T}$ 表示考虑了前 $i$ 个集合,$f(P)=S$,$f(Q)=T$ 的所有权值之和,考虑把第 $i$ 个集合加入 $P$ 或 $Q$ 或都不加入来进行转移。
可以把答案写成二元集合幂级数 $F(x,y)=\sum f_{S,T} x^S y^T$,那么 $F(x,y)=\prod x^U y^U+a_S x^S y^U+a_S x^U y^S$,乘法为与卷积。由于项数太少,不需要真的计算变换,枚举受到影响的部分就可以了,最后把答案整体做一个逆变换即可,复杂度 $O(6^n)$。
二元集合幂级数的变换和一元本质是一样的,因为你可以把 $y$ 的次数接在 $x$ 的次数后面来转化成等价的一元集合幂级数。
还是太慢了,发现修改是范围修改,对于 $x$ 和 $y$ 的其中一个次数是 $S$ 子集的位置影响是乘 $a_S+1$,对于 $x$ 和 $y$ 两个的次数都是 $S$ 子集的位置影响是乘 $2a_S+1$,对其他位置没有影响。
所以我们可以在 $x^S y^U$ 和 $x^U y^S$ 的两个位置分别乘 $a_S+1$,在 $x^S y^S$ 上挂一个 $\frac{2a_S+1}{(a_S+1)^2}$,最后做一个超集积就可以得到变换后的实际值。发现可能会出现 $0$ 做分母的情况,写个结构体,把每个值都存成关于 $0$ 的多项式来维护。因为求出变换后实际值之前只存在乘法,而逆变换的过程只存在加法,所以只有最低次项是有用的,只维护最低次项即可,复杂度 $O(n 4^n)$。
发现表的大小是 $4^n$ 的,保留表的情况下不可能继续优化,考虑跳过表直接算出最终答案。
首先表示一下表中逆变换之前 $x^S y^T$ 的系数。$a+1$ 对于 $S$ 和 $T$ 是独立的,而 $\frac{2a+1}{(a+1)^2}$ 有贡献要求对应集合包含 $S\cup T$。设:
$$
f_S=\prod_{S\subseteq T}(a_T+1),
$$
$$
g_S=\prod_{S\subseteq T}\frac{2a_T+1}{(a_T+1)^2}.
$$
则 $x^S y^T$ 的系数为 $f_S f_T g_{S\cup T}$。
答案是完成逆变换之后的 $x^S y^S$ 系数之和,称这种位置为答案位置,手模一下高维差分过程可以发现一个集合 $S$ 对它的一个子集 $T$ 的贡献系数是 $(-1)^{\lvert S\setminus T\rvert}$。这个时候我们发现 $S$ 每变化一位,$x^S y^S$ 的次数集合总大小变化量是 $2$!这意味着,对于任何一项 $x^S y^T$,它的系数对答案位置的影响系数是一个定值 $(-1)^{\lvert S\rvert+\lvert T\rvert}$!而它能影响到的答案位置个数是 $2^{\lvert S\cap T\rvert}$,所以它最终对答案的影响就是 $f_S f_T g_{S\cup T}(-1)^{\lvert S\rvert+\lvert T\rvert}2^{\lvert S\cap T\rvert}$。
我们终于可以把答案写出来了:
$$
\begin{aligned}
&\sum f_S f_T g_{S\cup T}(-1)^{\lvert S\rvert+\lvert T\rvert}2^{\lvert S\cap T\rvert}\\
=&\sum f_S f_T g_{S\cup T}(-1)^{\lvert S\rvert+\lvert T\rvert}2^{\lvert S\rvert+\lvert T\rvert-\lvert S\cup T\rvert}\\
=&\sum (-2)^{\lvert S\rvert}f_S (-2)^{\lvert T\rvert}f_T g_{S\cup T}2^{-\lvert S\cup T\rvert}
\end{aligned}
$$
后面两项 $g_{S\cup T}2^{-\lvert S\cup T\rvert}$ 有点突兀,我们枚举 $A=S\cup T$,那么我们需要计算的是:
$$
\sum_{S\cup T=A} (-2)^{\lvert S\rvert}f_S (-2)^{\lvert T\rvert}f_T
$$
这显然是一个或卷积。
所以我们高维后缀积求出 $f$ 和 $g$,然后计算这个或卷积,然后枚举 $S\cup T$ 统计答案即可,复杂度 $O(n 2^n)$。
## 子集卷积相关模板
### 子集卷积
子集卷积求的是:
$$
\sum_{S\cap T=\varnothing} f_S g_T x^{S\cup T}
$$
这种式子的意义也很明显,把集合分成不相交的两部分,每部分独立计算一些东西再合并起来,比如计算方案数之类的。
计算很容易,注意到 $S\cap T=\varnothing$ 和 $\lvert S\cup T\rvert=\lvert S\rvert + \lvert T\rvert$ 是等价的,所以把集合幂级数拆成 $n$ 个,新的 $f_{i,S}$ 在 $\lvert S\rvert=i$ 时为 $f_S$,否则为 $0$,随后计算 $H_i=\sum F_j G_{i-j}$,这里的乘法是或卷积,最后将满足 $\lvert S\rvert=i$ 的 $h_{i,S}$ 计入答案的第 $S$ 项中即可。这样做可以保证被统计到的都是满足 $\lvert S\cup T\rvert=\lvert S\rvert + \lvert T\rvert$,也就是 $S\cap T=\varnothing$ 的贡献。
没必要每次计算卷积时都做一遍变换,可以在转移前对每个序列做一次变换,转移过程中直接用,最后再进行逆变换就好了。这样对 $O(n)$ 个数列进行变换和逆变换的复杂度是 $O(n^2 2^n)$,转移过程中的复杂度是 $O(n^2 2^n)$,总复杂度是 $O(n^2 2^n)$。
### 半在线子集卷积
已知 $F$ 和若干函数 $\varphi_S$,求解形如
$$
g_S=\varphi_S(\sum_{T\subset S}g_T f_{S\setminus T})
$$
的问题。
下文中认为计算 $\varphi$ 的复杂度是 $O(1)$。
考虑按照 $\lvert S\rvert$ 分层求解,这样每一层就只会用到已知值。计算出这一层所有 $S$ 对应的和式之后套进 $\varphi$ 算一下就好。直接暴力做子集卷积是 $O(n^3 2^n)$ 的。
发现子集卷积过程中要按照 $\lvert S\rvert$ 分层,我们的求解过程也按照 $\lvert S\rvert$ 分层,所以每层求出来的就是后面子集卷积时要用到的数组,而且我们每次也只需要求解答案数组中的一层。每次求解出一层后计算变换后的结果,进行子集卷积时直接用就好了。每一层计算要 $n 2^n$,变换要 $n 2^n$,总复杂度 $n^2 2^n$。
### 集合幂级数求逆
给定 $F(x)$,求 $G(x)$ 使得 $F(x)G(x)=1$,乘法为子集卷积,保证 $f_0\neq 0$。
限制相当于:
$$
\sum_{T\subseteq S} g_T f_{S\setminus T}=[S=\varnothing]
$$
首先 $g_0=\frac{1}{f_0}$,对于剩下的我们有:
$$
\sum_{T\subseteq S} g_T f_{S\setminus T}=0
$$
所以
$$
g_S=-\frac{\sum_{T\subset S} g_T f_{S\setminus T}}{f_0}
$$
直接套半在线子集卷积模板即可。
### 集合幂级数 $\exp
先放一下定义:
e^{F(x)}=\sum \frac{F^i(x)}{i!}
其中乘法是子集卷积。
为了让级数收敛,需要让 f_0=0。由于子集卷积的集合一定越来越大,可以证明这种情况下 F^{n+1}(x)=0,级数一定收敛。
有一个显然的组合意义:把某个集合划分成任意数量的子集,一个划分方案的权值是划分出的子集的权值之积,求每个集合所有划分方案的权值之和。
这个意义在 这篇文章 中多次出现。
考虑依据组合意义求解该问题。考虑一个暴力的 O(3^n) dp:枚举每个集合中最大元 u 所在的子集进行转移,有:
g_S=\sum_{T\subseteq S,u\in T} f_T g_{S \setminus T}
最后 G(x) 就是 e^{F(x)}。
考虑对于 u 分层转移,设 F_i(x) 是 F(x) 中只保留最大元恰好为 i 的部分,G_i(x) 是只考虑 F 中最大元不大于 i 的集合时计算出的答案,有递推式:
G_i(x)=G_{i-1}(x)F_i(x)+G_{i-1}(x)
其中乘法是子集卷积。
发现第 i 轮时 F 和 G 只有前 2^i 是有值的,所以做子集卷积时只考虑这些位置,复杂度是:
\sum_{i=0}^n i^2 2^i=O(n^2 2^n)
这个做法没有用到逆元,也就不要求模数为质数。
实际计算的时候发现 f 只有最高位为 i 的 2^{i-1} 有值,而 g 的最高位只有 i-1,所以在第 i 位上只有 1|0\to 1 的转移,那么我们可以忽略这一位,把 f 整体右移,进行运算之后把答案整体左移回来,这样每次求解的范围变为原先一半,可以显著降低常数。
没用逆元,可以直接通过加强版。
集合幂级数 \ln
定义是满足 e^{G(x)}=F(x) 的 G,保证 f_0=1。
直接上组合意义,其实就是把 \exp 要干的活反过来,已知每个集合所有划分方案的权值和,求一个集合本身的权值。
这个意义也在 这篇文章 中多次出现。
发现把集合划分成它自己是一个合法方案,所以 f_S 里有 g_S 这一项,想法把其他项扣掉即可。
其实就是把 dp 反着做一遍,依旧枚举 S 中的最大元 u:
g_S=f_S-\sum_{T\subset S,u\in T} f_{S \setminus T} g_T
还是对于 u 分层转移,但这次的转移式变成了半在线卷积,套半在线卷积的方法做就好了。