专栏文章

[数学] 哈集幂 10 元教程（1，不一定有 2）

FFelix72
算法·理论参与者 16已保存评论 16

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
16 条
当前快照
1 份
快照标识符
@mjhekdhg
此快照首次捕获于
2025/12/23 01:01
2 个月前
此快照最后确认于
2026/02/19 01:26
10 小时前
查看原文
什么我们集合幂级数十元教程，竟然这么的秀吗？
前情提要。虽然那个题 O(3n)O(3^n) 直接过了但是我思来想去觉得哈集幂还是得学。毕竟这东西不学正赛要炸 ∇(˃ ⌑ ˂ഃ )∇
本文不会介绍但是需要知道的：
  • 高维前缀和
  • FFT 优化乘法的思想（化为某点值形式、对位相乘、从点值形式化回去）。不需要真的会 FFT，但是建议先去学。
  • 基本的多项式和形式幂级数思想（知道 xnx^n 中的 xx 不是一个数而是一个下标状物）。不需要会多项式 exp，ln，求逆等等。
鉴于集合幂级数的初学者都知道上面三个东西，本文可以说是相当 00 基础的。
Info
不保证本文的数学用词严谨性。仅保证这是面向初学者的集合幂级数教学，因此措辞会相对随意。

1. 集合幂级数引入

如果学过背包或者多项式乘法，你就会知道这类问题的本质是 ai×bja_{i} \times b_{j} 贡献到了 ci+jc_{i + j}。我们还是新手时叫他背包转移，学了点数学后就发现这个叫做乘法，即把两个关于 xx 的多项式相乘，xnx_n 的系数就是 DP 数组的 cnc_n。
我们考虑魔改 DP 形式。现在假设我在做状压 DP，希望 aS×bTa_{S} \times b_{T} 贡献到 cRc_R，其中 S∪T=RS \cup T = R。我们考虑这个东西能不能用 xx 的幂次式表示？不妨认为 xx 的幂次可以是一个集合（“集合次幂”不需要具体的意义，因为 xx 不是一个数），那么我们的 a,ba, b 数组可以看作关于 xx 的两个式子 A(x),B(x)A(x), B(x)，我们定义 A(x)A(x) 乘 B(x)B(x) 为 C(x)C(x)，其中 C(x)C(x) 里面 xRx^R 的系数是所有 S∪T=RS \cup T = R 的 A(x)A(x) 的 xSx_S 的系数和 B(x)B(x) 的 xTx_T 的系数乘积之和。
你看这个自然语言描述系数很不方便啊，不妨令 [xS]A(x)[x^S]A(x) 表示 AA 式子中 xSx^S 这一项的系数。
那么我们就定义了 [xR]C(x)=∑S∑T[xS]A(x)×[xT]B(x)[S∪T=R][x^R]C(x) = \sum_S \sum_T [x^S]A(x) \times [x^T]B(x) [S \cup T = R]，后面这个中括号是艾弗森括号。

2. 卷积运算

2.0 定义

上面用 S∪TS \cup T 举例说明了我们是怎么把“贡献”这种抽象的东西描述为“乘法”这类形象的数学表达的。
但是要知道乘法本身就有多种意思，比如 FFT 和 FWT 做的事情我们都叫做加速卷积。
这里面具体的区别其实就是“贡献”的条件不同。多项式乘法中“贡献”的条件是 i+j=ki + j = k，上面举的例子中贡献条件是 S∪T=RS \cup T = R，那么我们自然可以定义多种不同的贡献条件，对应出不一样的卷积。
比如我们来看 FWT 模板题题面：
给定长度为 2n2^n 两个序列 A,BA,B，设
Ci=∑j⊕k=iAj×BkC_i=\sum_{j\oplus k = i}A_j \times B_k
分别当 ⊕\oplus 是 or, and, xor 时求出 CC。
这三种贡献形式就可以分别被叫做或卷积、与卷积、异或卷积。
下面，我将讲解不同种类的卷积应当怎样实现。

2.1 或卷积

FMT，快速莫比乌斯变换，即对于 A(x)A(x) 的每个 SS，都计算出 ∑T⊆S[xT]A(T)\sum_{T \subseteq S} [x^T]A(T)。你发现这简直就是高维前缀和，可以直接用 SOSdp 求解。
但是你尚不知道其作用。FMT 就是单纯求一个前缀和吗？
显然并不只有那么简单。我们知道，两个多项式用 DFT 处理一下之后可以做到 O(n)O(n) 相乘，还能用 IDFT 变回去，那么多项式乘法就这么实现了；这里 FMT 的作用和 FFT 是一致的，即我们可以用 FMT 处理两个式子 A(x),B(x)A(x), B(x)，处理完得到 FMT(A(x)),FMT(B(x))FMT(A(x)), FMT(B(x))，再 O(2n)O(2^n) 乘出 FMT(C(x))FMT(C(x))，最后把 FMT(C(x))FMT(C(x)) 转化为 C(x)C(x)，就直接加速了卷积。
FMT 能够加速的卷积是与卷积和或卷积。
它的原理是什么？拿或卷积举例子，其要求 S∪T=RS \cup T = R。不妨放宽条件，先考虑 S∪T⊆RS \cup T \subseteq R 这个情况。如果你得到了所有对应的 [xR]C(x)[x^R]C(x)，那么求解原答案只是一个高维差分的事情（即高维前缀和的逆过程）。于是考虑求解 S∪T⊆RS \cup T \subseteq R 的 [xR]C(x)[x^R]C(x)。
我们发现 S∪T⊆RS \cup T \subseteq R 有结合律，即它等价于 S⊆RS \subseteq R 且 T⊆RT \subseteq R，SS 和 TT 独立了，那么自然可以高维前缀和之后对位相乘。这样我们求出了 [xR]C(x)[x^R]C(x)。
与卷积和或卷积没有任何本质区别，只是把 00 和 11 的地位换了。

2.2 异或卷积

这部分的代码存在其他理解方式，学不懂可以参考模板题解，换个方向。
FWT，快速沃尔什变换，同样是加速计算用的，它可以加速异或卷积。
考虑异或卷积 A(x)×B(x)=C(x)A(x) \times B(x) = C(x)（此处的乘号是异或卷积意义下的）。
我们有 [xR]C(x)=∑S∑T[S⊕T=R]×[xS]A(x)×[xT]B(x)[x^R]C(x) = \sum_S\sum_T [S \oplus T = R] \times [x^S]A(x) \times [x^T]B(x)。S⊕T=RS \oplus T = R 等价于 [S⊕T⊕R]=∅[S \oplus T \oplus R] = \emptyset。
这个艾弗森括号必须拆了，不然 SS 和 TT 不可能独立。
设 nn 是集合元素个数，引入空集判别式如下：
[S is empty]=12n∑T(−1)∣T∩S∣[S \ is \ empty] = \frac{1}{2^n} \sum_{T} (-1)^{|T \cap S|}
证明并不难。
由此消去艾弗森括号得到
[xR]C(x)=12n∑S∑T∑Q(−1)∣(S⊕T⊕R)∩Q∣×[xS]A(x)×[xT]B(x)[x^R]C(x) = \frac{1}{2^n}\sum_S\sum_T \sum_Q (-1)^{|(S \oplus T \oplus R) \cap Q|} \times [x^S]A(x) \times [x^T]B(x)
这个 S⊕T⊕RS \oplus T \oplus R 挺有说法的！我们知道 −1-1 的若干次幂的值之和其奇偶性相关，不难拆分出
(−1)∣(S⊕T⊕R)∩Q∣=(−1)∣S∩Q∣×(−1)∣T∩Q∣×(−1)∣R∩Q∣(-1)^{|(S \oplus T \oplus R) \cap Q|} = (-1)^{|S \cap Q|} \times (-1)^{|T \cap Q|} \times (-1)^{|R \cap Q|}
于是
[xR]C(x)=12n∑Q(−1)∣R∩Q∣(∑S(−1)∣S∩Q∣×[xS]A(x))(∑T(−1)∣T∩Q∣×[xT]B(x))[x^R]C(x) = \frac{1}{2^n} \sum_Q (-1)^{|R \cap Q|}(\sum_S (-1)^{|S \cap Q|} \times [x^S]A(x))(\sum_T (-1)^{|T \cap Q|} \times [x^T]B(x))
一个惊人的事实是，SS 和 TT 已经独立了。现在我们可以定义 FWT(A(x))FWT(A(x))，其中 [xQ]FWT(A(x))=∑S(−1)∣S∩Q∣×[xS]A(x)[x^Q]FWT(A(x)) = \sum_S (-1)^{|S \cap Q|} \times [x^S]A(x)。我们先计算出 FWT(A(x))FWT(A(x)) 和 FWT(B(x))FWT(B(x))，再对位相乘得到一个新式子。你发现乘出来的这个式子右半边就是 FWT(C(x))FWT(C(x)) 啊，于是考虑逆变换，直接换回去卷积就做完了。
形式上的，就是：
[xR]C(x)=12n∑Q(−1)∣R∩Q∣[xQ]FWT(C(x))[x^R]C(x) = \frac{1}{2^n}\sum_Q(-1)^{|R \cap Q|}[x^Q]FWT(C(x))
现在我们需要做的，就是快速进行如下变换：
F(x)→FWT(F(x)),FWT(F(x))→F(x)F(x) \to FWT(F(x)), FWT(F(x)) \to F(x)
只要能在合理复杂度内进行这两个操作，那么异或卷积也被解决了。
考虑你有一棵 01-Trie\text{01-Trie}，你已经对左右子树求出了 FWTFWT 变换，则稍加推导就可以把信息合并起来了。
三种变换的实现CPP
// 快速莫比乌斯变换 
inline void OR(long long *f, int type)
{
	// type = 1 表示高维前缀和，否则表示高维前缀差分 
	for(int i = 1; i <= n; ++i)
		for(int j = 0; j < (1 << n); j += (1 << i))
			for(int k = j; k < j + (1 << (i - 1)); ++k)
				Plus(f[k + (1 << (i - 1))], mod + f[k] * type);
}
inline void AND(long long *f, int type)
{
	// type = 1 表示高维后缀和，否则表示高维后缀差分 
	for(int i = 1; i <= n; ++i)
		for(int j = 0; j < (1 << n); j += (1 << i))
			for(int k = j; k < j + (1 << (i - 1)); ++k)
				Plus(f[k], mod + f[k + (1 << (i - 1))] * type);
}
// 快速沃尔什变换 
inline void XOR(long long *f, int type)
{
	long long iv = qpow(qpow(2, n), mod - 2);
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 0; j < (1 << n); j += (1 << i))
		{
			for(int k = j; k < j + (1 << (i - 1)); ++k)
			{
				long long n1 = f[k], n2 = f[k + (1 << (i - 1))];
				f[k] = (n1 + n2) % mod, f[k + (1 << (i - 1))] = (n1 - n2 + mod) % mod;
			}
		}
	}
	if(type == -1)
	{
		for(int i = 0; i < (1 << n); ++i) f[i] = f[i] * iv % mod;
	}
}
上面所谓的另一种理解方式是直接上分治算法讨论，相较于这个推式子是要简单一些。

2.3 子集卷积

回顾或卷积的定义，AS×BT→CS∪TA_S \times B_T \to C_{S \cup T}。
回忆做状压 DP 时，很多题目要求的是 SS 和 TT 没有交！这种时候或卷积就无能为力了，我们不会哈集幂的时候都是 O(3n)O(3^n) 枚举子集的。
现在介绍或卷积的改造，可以有效处理不交这个限制。
首先明确，我们想要的是
[xR]C(x)=∑S∩T=∅,S∪T=R[xS]A(x)×[xT]B(x)[x^R]C(x) = \sum_{S \cap T = \emptyset, S \cup T = R} [x^S]A(x) \times [x^T]B(x)
这个不交的限制等价于 ∣S∣+∣T∣=∣S∪T∣|S| + |T| = |S \cup T|。
我们把 AA 拆成 n+1n + 1 个级数。其中 Ai,SA_{i, S} 在 ∣S∣=i|S| = i 时和原来的 ASA_S 相同，否则为 00。
我们用 O(n22n)O(n^22^n) 的时间把 nn 个 AA 和 nn 个 BB 全部变换好，再用同样时间把他们两两相乘贡献到 nn 个 CC 上面，贡献方式是 Ai×Bj→Ci+jA_i \times B_j \to C_{i + j}，这个乘号表示或卷积。
你发现你要的原 [xR]C(x)[x^R]C(x) 就是 C∣R∣,RC_{|R|, R}，真不错。

2.4 三种变换的其他理解方式

【待补充】

2.5 kk 维 FWT 扩展

【待补充】

2.6 半在线卷积

有时哈集幂也会出现自己卷自己的情况，比如我们需要计算
fS=∑T⊂SfT×gS−Tf_{S} = \sum_{T \sub S} f_{T} \times g_{S - T}
如果这个级数是一般的形式幂级数，我们可以用分治 FFT，即 cdq 分治解决。
但是这是哈集幂，不能分治 FFT 了。我们思考分治 FFT 把在线变成离线的原理，是给卷积的贡献过程划分了顺序。我们也可以尝试给集合幂级数的卷积“确定顺序”。
不妨按照 ∣S∣|S| 分类，对于 i:0→ni : 0 \to n，每次只计算出 ∣S∣=i|S| = i 的 fSf_{S}，然后再把 ∣S∣=i|S| = i 的 fSf_{S} 往后面贡献。这个实际上和分治 FFT 的思想是大同小异的，只是分治 FFT 每次对半分，前面贡献后面；这个集合幂级数卷积是 ∣S∣=i|S| = i 贡献到 ∣S∣>i|S| > i 的位置。
你将会在 3.2 部分看到半在线卷积的具体实现。

3. 集合幂级数的常用函数

3.1 exp⁡\exp

exp⁡\exp 表示 ee 的幂次。我们在多项式里面也能看到求 exp⁡\exp 环节（笔者不会）。为什么要学求 eF(x)e^{F(x)}？这是因为有泰勒展开 ex=∑i=0∞xii!e^x = \sum_{i = 0}^{\infin} \frac{x^i}{i!}。
  • 把一个多项式 F(x)F(x) 代入 xx 得到 eF(x)=∑i=0∞F(x)ii!e^{F(x)} = \sum_{i = 0}^{\infin}\frac{F(x)^i}{i!}。我们把 F(x)F(x) 的 ii 次方定义为卷积，就能发现它居然在描述有标号元素构成的集合划分为任意个非空子集的总方案数。
  • 把一个形式幂级数 F(x)F(x) 代入 xx 得到 eF(x)=∑i=0∞F(x)ii!e^{F(x)} = \sum_{i = 0}^{\infin}\frac{F(x)^i}{i!}。我们把 F(x)F(x) 的 ii 次方定义为子集卷积，就能发现它居然在对所有集合 SS 描述把 SS 划分为若干小集合的总方案数。
由于是级数形式，你看这个总方案数还能带权，我们发现这个 exp⁡\exp 貌似是很有用的！
换句话说，集合幂级数的 exp⁡\exp 解决的是这样一个问题：
有 nn 个元素，并给定 2n2^n 种权值。你需要对于每一种可能的集合，都求出其所有划分方式的权值之和。权值定义为划分出的每个集合的权值乘积。
我们考虑 DP 求解。若用普通状压 DP 解决这个问题，一般的方法是枚举 highbit\text{highbit} 所在的集合 TT，然后 dpS−T×wT→dpSdp_{S-T} \times w_T \to dp_S。
这里我们沿用这个方法。考虑枚举 highbit\text{highbit} 的元素 IDID，然后我们要做的就是 DP 的转移部分。我们看这个转移的 dpS−T×wT→dpSdp_{S - T} \times w_T \to dp_S 正是我们的子集卷积，因此用前面的 FMT 加速即可。
实现可以参考这篇题解，写的是相当的清楚！

3.2 ln⁡\ln

什么是 ln⁡\ln？ex=ye^x = y，则 ln⁡y=x\ln y = x。
可以看出，x→exp⁡(x)x \to \exp(x) 和 x→ln⁡(x)x \to \ln(x) 是一正一反两个过程。求 ln⁡\ln 可以被理解为 exp⁡\exp 的某种“反演”。
那么其组合意义自然也是相对应的：
有 nn 个元素，并给定 2n2^n 种权值。一个集合的美丽度定义为在所有划分方式中划分出的每个集合的权值乘积之和。现在你只知道美丽度，求初始权值。
设权值 ff，美丽度 gg。有：
fS=gS−∑T⊂S,lowbit(S)=lowbit(T)gTfS−Tf_{S} = g_{S} - \sum_{T \sub S, \text{lowbit}(S) = \text{lowbit}(T)} g_Tf_{S - T}
则我们可以先枚举 lowbit\text{lowbit}，然后使用半在线卷积加速。
核心代码CPP
for(int ID = 1; ID <= n; ++ID)
{
  // 枚举 highbit 是哪个元素 
  
  int cur = (1 << (ID - 1)); // ID 的二进制编码 
  // 考虑对 f[S] = g[S] - \sum f[T] * g[S - T] 进行半在线卷积求解 
  // 先对 f, g 进行 FMT 
  for(int i = 0; i < ID; ++i) FMT(g[i], ID - 1, 1);
  for(int i = 1; i <= ID; ++i) FMT(f[i] + cur, ID - 1, 1);
  for(int i = 1; i <= ID; ++i)
  {
    // 半在线卷积，处理到 i 时 |S| = i 的 f[S] 已经计算完成 
    FMT(f[i] + cur, ID - 1, -1); // 进行 IFMT 求出贡献真实值 
    // 计算出 f 
    for(int j = 0; j < cur; ++j)
      f[i][j + cur] = g[i][j + cur] - f[i][j + cur];
    FMT(f[i] + cur, ID - 1, 1); // 再进行 FMT 准备后续乘法 
    for(int j = i + 1; j <= ID; ++j) // 贡献到 j 
      for(int k = 0; k < cur; ++k)
        f[j][k + cur] += f[i][k + cur] * g[j - i][k];
  }
  for(int i = 0; i < ID; ++i) FMT(g[i], ID - 1, -1);
  for(int i = 1; i <= ID; ++i) FMT(f[i] + cur, ID - 1, -1);
}

3.3 逆

逆，即 1x\frac{1}{x}，对于一个集合幂级数 A(x)A(x) 来说就是一个满足 A(x)×B(x)=1A(x) \times B(x) = 1 的 B(x)B(x)。此处的乘号是子集卷积。
不妨解方程，A(x)×B(x)=1A(x) \times B(x) = 1 首先要求 [x∅]A(x)×[x∅]B(x)=1[x^\emptyset]A(x) \times [x^\empty]B(x) = 1。在模质数的情况下求整数逆元就可以了。
然后考虑 S≠∅S \neq \emptyset 的 [xS]B(x)[x^S]B(x)。此时有方程如下：
∑T⊆S[xT]A(x)×[xS−T]B(S−T)=0\sum_{T \subseteq S} [x^T]A(x) \times [x^{S - T}]B(S - T) = 0
这是因为 A(x)×B(x)A(x) \times B(x) 除了常数项之外全是 00。
我们要求的是 [xS]A(x)[x^S]A(x)，你发现这个式子把 [xS]A(x)×[x∅]B(x)[x^S]A(x) \times [x^\emptyset]B(x) 放到右边之后是一个半在线卷积形式。
于是套用半在线卷积的算法即可。

4. 小结

现在你可以做的题：
后面两题的质数版本没必要做，反正上文已经讲了通用做法了。
下一篇（如果有的话）集合幂级数教程将讲解怎么使用哈集幂解题。
（已褪色.jpeg）

评论

共 16 条评论，欢迎与作者交流。

正在加载评论...