希望大家一直记得我。
“希望大家永远忘了我。”
这是一篇集合幂级数学习笔记
阅前须知：作者神志不清，文章可能出现大量错别字与病句。如有发现不要请不要指出，就让它错在哪里吧
定义
首先来理解形式幂级数，即大家所熟知的多项式：\(F = \sum a_ix^{i}\)，它表示一个函数本身
而集合幂级数表示的是一个定义域 \(S\subseteq U=\{1,\cdots,n\}\) 的函数的取值表，即 \(F = \sum\limits_{S\subseteq U}f_Sx^S\) 表示对于所有 \(S\subseteq U\)，函数在 \(S\) 处的取值是 \(f_S\)。这里 \(x^S\) 没有实际意义，只是一个占位符，表示这是 \(S\) 处的取值
后文可能会用 \(x=\sum\limits_{p\in S}2^{p-1}\) 来代替 \(S\)
运算
加法
和多项式加法一样，每一位对应相加即可，注意要保证全集相等才能相加
并/交/异或卷积
即 \(h_S=\sum\limits_{X\cup/\cap/\oplus Y=S}f_Xg_Y\)，与多项式一样，使用 FWT 解决。这里只讲或卷积，其他情况同理
大致思想与 NTT 类似，做变换后逐位相乘再做逆变换
令 \(f^\prime_S=\sum\limits_{X\subseteq S}f_X\)，那么：
\(F^\prime\) 也很好求，初始值令 \(F^\prime=F\) 然后递归求解，设当前序列长度为 \(2^n\)，\(\forall x\in[2^{n-1},2^n-1],f^\prime_x \gets f^\prime_x+f^\prime_{x-2^{n-1}}\)
逆变换就是把加法改为减法，证明同理
子集卷积
P6097 【模板】子集卷积
即 \(h_S=\sum\limits_{X\cup Y\ \text{and}\ X\cap Y=\varnothing}f_Xg_Y\)，比普通的或卷积多了一个没有交的条件
暴力算法是 \(O(3^n)\) 枚举每一种元素的状态，无法通过 \(n=20\) 的数据
令 \(f^\prime_{i,S}=\sum\limits_{X\subseteq S\ \text{and}\ |X|=i}f_X\)，对每一个 \(i\in[1,n]\) 做一次 FWT 即可得到，这一步的复杂度为 \(O(2^nn^2)\)
我们发现 \(|X|+|Y|=|S|\ \text{and}\ X\cup Y=S\) 是 \(X\cap Y=\varnothing\ \text{and}\ X\cup Y=S\) 的充分条件，于是：
这部分复杂度也是 \(O(2^nn^2)\)，最后对 \(h^\prime_{i,S}\) 做一遍 IFWT，总复杂度 \(O(2^nn^2)\)
集合幂级数 \(\text{exp}\)
P12230 【模板】集合幂级数 exp
即 \(G=e^{F}=\sum\limits_{i=0}^{\infty}\frac{F^{i}}{i!}\)，\(F^{i}\) 指 \(F\) 与自己做 \(i\) 次子集卷积；特别地，\(F^{0}=1\)
根据定义，我们可以发现 \(F^{i}_S=\sum\limits_{S_1\cup S_2\cup \dots \cup S_i\ \text{and}\ |S_1|+|S_2|+\dots+|S_i|=|S|}\prod\limits_{j=1}^{i}f_{S_j}\)。同样的，我们定义 \(f^\prime_{i,S}=\sum\limits_{X\subseteq S\ \text{and}\ |X|=i}f_X\)
我们枚举 \(S\)，有 \(g^{\prime}_i=\sum\limits_{k=0}^{\infty}\frac{1}{k!}\sum\limits_{i_1+i_2+\dots+i_k=i}\prod\limits_{j=1}^{k}f^{\prime}_{i_j,S}\)。这就是 \(F^{\prime}_{i}\) 的多项式 \(\text{exp}\)，可以直接 \(O(n^2)\) 递推算
然后就做完了
例题
P13275 [NOI2025] 集合
还不会
P11834 [省选联考 2025] 岁月
还不会