集合幂级数入土

· · 个人记录

如有雷同纯属抄的

前置

令集合中的元素为 0\sim n-1，集合为 0\sim 2^n-1。

在集合幂级数相关问题中，我们更倾向于研究子集卷积，或者说不交并，记作叉乘 [x^S](f\times g)=\sum_{X\cap Y=\varnothing,X\cup Y=S}[x^X]f\cdot[x^Y]g。

为方便求解，通常会使用占位多项式将子集卷积转化为或卷积，记或卷积为 [x^S](f*g)=\sum_{X\cup Y=S}[x^X]f\cdot[x^Y]g，另记对位相乘 [x^S](f\cdot g)=[x^S]f\cdot [x^S]g。

令 f 的占位多项式表示为 f'，即 [x^S]f'=[x^S]f\cdot x^{|S|}。由经典方法，\text{FMT}(f')\cdot \text{FMT}(g')=\text{FMT}((f\times g)')，这里的对位相乘为多项式卷积，即 [x^S](f'\cdot g')=[x^S]f'* [x^S]g'。

复合及其他高级运算

有下标为 0\sim n 的多项式 H，令 H 与集合幂级数 F 的复合为 H(F)=\sum_{i=0}^n [x^i]H\cdot F^i。

用 FMT 表述幂次：[x^S]\text{FMT}(H(F)')=\sum_{i=0}^n[x^i]H\cdot ([x^S]\text{FMT}(F'))^i。

复杂度为 FMT 加上 2^n 次多项式复合。直接实现是 O(2^nn^3) 的。

注意到 \exp、\ln、求逆、\exp_{\leq k} 等操作都符合上述形式，即 \exp(F)=\sum_{i=0}^n\dfrac{1}{i!}F^i（这里钦定 F_0=0 以保证不会无限叠加，也保证了枚举上界为 n），\ln(1+F)=\sum_{i=1}^n\dfrac{(-1)^{i+1}}{i}F^i。

而在 FMT 后的多项式复合即为 多项式 \exp/多项式 \ln/多项式求逆/多项式 \exp_{\leq k}，都是可以 O(n^2) 做的，所以复杂度为 O(2^nn^2)。

模板：P12230 P12231 P12232 P6570 LOJ#154

UOJ#94. 【集训队互测2015】胡策的统计

令集合 S 的子图个数为 [x^S]g_S=2^{edgecnt(S)}，连通子图为 f，显然有 g=\exp(f)，那么 f=\ln g。

而答案 h 相当于 [x^i]H=1 对 f 的复合 h=H(f)。求一个 \dfrac{1}{1-f} 即可。

QOJ#5411. [CTT 2020 Day 4] 杏仁

从 T 开始跑一个 O(2^nn^2) 的 DP，预处理每个集合，链头为 u 的方案数。

普通的问题只需要求一个子集 exp 就好了。强制含链头 u 枚举一下 u 所在集合，直接调用补集的 exp 即可。

QOJ#6954. Almost Acyclic

考虑题目中的环交集：

树计数可以用行列式算。

基环树计数，先用哈密顿 DP 计数出环，然后用行列式算其它点的生成树方案。

基环杏仁计数，枚举 S 和 T，对每个集合处理出树计数并选择两个点连接 S 和 T，或者只连接其一，将其作为一条杏仁链，子集 exp。

森林计数，对每个集合处理出树计数并与 x 连通，子集 exp。

最后去个重。

LOJ#6673. EntropyIncreaser 与山林

与上述题目相同地，先求出每个点度数都是偶数的方案数，然后求个 \ln 即可。

不难发现前者是 2^{|E|-|V|+tot(E)}。

ABC294Ex K-Coloring

首先有一个 O(2^nn^2) 的做法：令 [x^S]G 为集合 S 是否为一个独立集（包含空集），那么答案为 [x^U]F^k。

考虑广义串并联图缩边思想，\leq 1 度点显然可以直接缩掉。

对 2 度点，考虑令 G_1 表示把这个点删掉后的图，G_2 表示把这个点删掉并给两个邻居连上边后的图，那么有 ans(G)=(K-2)ans(G_1)+ans(G_2)。

这样缩边过后点数不超过 \dfrac{2}{3}m，而分裂图的操作可以说明对复杂度只有常数影响。

CF1326F2 Wise Men (Hard Version)

容斥，将 0 看作没有限制。

你发现枚举集合算答案是不优秀的，因为每个 1 连续段可以任意排列，相当于只有拆分数种状态是有用的。

预处理每个集合成链的方案数 f，那么假设搜出了拆分数 p，贡献相当于 \prod_{i}\sum_{|S|=p_i}f_S。后者只有 O(n) 类，可以在搜索前把 FMT 做好，每次直接点乘起来即可。

事实上由于搜了拆分数，这里的乘法直接认为是或卷积即可，因为若卷积起来的两个集合有交就贡献不到 U 上去了。

逐点牛顿迭代法

说人话是增量法，不需要任何牛顿迭代知识储备。一个用处是在 H 任意时把上述 O(2^nn^3) 暴力优化到 O(2^nn^2)：

摒弃上面的推导，从头开始。考虑求 H(F)=\sum_{i=0}^n \dfrac{[x^i]H}{i!}\cdot F^i ，注意多了一个除以 i!。

考虑从低往高枚举位，令集合幂级数 \text{DP}_{i,j} 表述考虑了前 i 位，钦定还有 j 次乘法操作。初值 \text{DP}_{0,j}=([x^i]H)\cdot x^{\varnothing}。

添加第 i 位，转移为 \text{DP}_{i,j}\leftarrow \text{DP}_{i-1,j}+\text{DP}_{i-1,j+1}\times F[2^{i-1},2^i-1]。后者表示 F 含 i 且不含 >i 的项。

因为钦定了高位，所以 i! 被自然除去了。

每次做 n-i 次长度为 i 的子集卷积，复杂度为 O(\sum(n-i)2^ii^2)=O(2^nn^2)。常数有点大。

LOJ#155 Tutte 多项式

本题为一切经典子图计数问题的祖宗。

复述一下：求 \sum_{A\subseteq E}(X-1)^{tot(A)-tot(E)}(Y-1)^{tot(A)+|A|-|V|}。

注意不能直接拆贡献，因为用到了 0^0=1 这个东西（这也说明了当 X, Y 都 >0 时有小常数写法）。我们要在接下来的运算中保持指数非负。

首先默认 tot(E)=1，显然原图每个连通块是独立的。

对于一个连通块，其对 Y 项的贡献为 [x^S]F=\sum_{E'}(Y-1)^{|E'|-(|S|-1)}。

而答案为 G=\sum_{i\geq 1}\dfrac{(X-1)^{i-1}}{i!}F^i，特判 X=1，把 (X-1)^i 放进 F 里其实是 \exp 的形式。

预处理 F，考虑逐点牛顿迭代法（增量法），假设加入 i 时，S 中的点已经成为一个连通块，那么 i 与 S 连通的贡献为 \sum_{j=1}^{tot}\dbinom{tot}{j}(Y-1)^{j-1}=\dfrac{Y^{tot}-1}{Y-1}，依旧特判 Y=1。

每次需要做一个大小为 i-1 的子集 exp，复杂度仍是 O(2^nn^2) 的，常数比复合小多了。

DAG 容斥

刻画 DAG 的方法：每次取出全部无出度点，钦定它们与其它点之间的边，递归子问题。

但实际上并不能保证每次取出的点是全部的零度点。

考虑容斥。令一个集合 S 的容斥系数为 \text{coef}_S，假设真正的零度点集合为 U，我们需要使 \sum_{S\subseteq U,S\ne \varnothing} \text{coef}_S=1，由二项式定理，取 \text{coef}_S=(-1)^{|S|+1} 即是满足条件的。

P6846 [CEOI 2019] Amusement Park

首先需要一个脑筋急转弯：DAG 的反图也是 DAG，所以原问题的答案 等于 DAG 定向方案数乘 \dfrac{m}{2}。

令 [x^S]G=(-1)^{|S|}\cdot [\text{内部没有边}]，表示一个集合是合法零度集的容斥系数，则答案为带顺序的合并 F=\sum_{i=0}G^i=\dfrac{1}{1-G}。求逆即可。

P11714 [清华集训 2014] 主旋律

强连通图个数 = 任意图 - 不强连通图的个数。考虑对缩点后 DAG 计数，相当于求缩点后有 >1 个强连通分量的方案数。

钦定零度强连通分量集合，容斥系数为 (-1)^{tot(S)} 为强连通分量个数。

实际上并不关心 tot(S) 的具体值，DP 记录一下 tot 的奇偶性即可，即选择了奇数/偶数个强连通分量的方案数。

这题 O(3^n) 做就行了。

P10221 [省选联考 2024] 重塑时光

相当于有一个 DAG，划分若干段，每一段内部是合法拓扑序，段之间存在合法整段的拓扑序。

计数的系数与总共取了多少段有关，这部分不是重点，我们先把它记进状态，后面再说。

刻画一下段之间的 DAG，称两个段 A 到 B 有连边的意思是存在 p\in A,q\in B，p\to q 在原图上有连边。这样表述以后我们就可以考虑对段之间进行 DAG 容斥了。

令 g_{S,x} 表示集合 S 中选了 x 个非空段，每段之间都是（在段意义上）零度的。f_{S,x} 同理表示合法的（段）DAG 的方案。

令 $h_S$ 为 $S$ 内部的合法拓扑序个数，$g$ 的转移直接枚举一个子集的 $h$ 即可。 这样是 $O(3^nn^2)$ 的。考虑把那个很膈应的加法卷积给搞掉。一个技巧是卷积只关心前 $n$ 位，即 $n$ 次多项式，改成 $0\sim n$ 的点值后就把卷积改成点乘了，最后插值回来即可。 不过由于现在没有记录 $x$ 了，所以要用上一题的方法记录一下奇偶性。 #### P11834 [省选联考 2025] 岁月 有一篇写的比较凌乱的笔记，懒得修缮了。 ## FWT/FMT的展开式及多元 GF $$[x^S]\text{FWT}(F)=\sum_{T}(-1)^{|T\cap S|}[x^T] F$$ $$[x^S]\text{FMT}(F)=\sum_{T\subseteq S}[x^T] F$$ $$[x^S]\text{IFMT}(F)=\sum_{T\subseteq S}(-1)^{|S/T|}[x^T] F$$ FWT 的本质与集大成者：QOJ#9562. 欧伊昔。这部分写起来太长，后面有空再写。 #### CF1411G No Game No Life 默认乘法是异或卷积。 算出每个点的 SG 函数，令其集合幂级数为 $F$，答案相当于 $[x^{\varnothing}]\sum_{i=0}\dfrac{1}{(n+1)^{i+1}}F^i$。把系数拆进 F 里面，相当于 $\dfrac{1}{(n+1)(1-F)}$。 FWT 后对点值每一项都求逆即可。如果你质疑正确性，其实这与 FMT 的复合并无差别。 #### UOJ#310. 【UNR #2】黎明前的巧克力 首先需要知道 $[x^S]\text{FWT}(F)=\sum_{T}(-1)^{|T\cap S|}[x^T]F$，这个式子可以通过 FWT 的本质看出。光会背板是不行的。 两个值相等相当于异或起来等于 $0$，相当于求 $[x^\varnothing]\prod_i (1+2x^{a_i})$。 观察一下后者的 FWT，$[x^S]\text{FWT}(F)=\prod_i(1+2\times (-1)^{S\cap a_i})$，令 $cnt(S)$ 表示有多少个 $a_i$ 与 $S$ 交集为奇数，则 $[x^S]\text{FWT}(F)=(-1)^{cnt(S)}\times 3^{n-cnt(S)}$。 直接求 $cnt(S)$ 不低于 $O(3^n)$ 枚举子集。 思路打开，另辟蹊径：假设求得了 $\sum_i(1+2\times (-1)^{S\cap a_i})$，就可以解方程得到 $cnt(S)$。而前者为 $\sum_i[x^S]\text{FWT}(F_i)=[x^S]\text{FWT}(F_1+F_2+\cdots +F_n)$，这样只需要一次 FWT 就可以得到 $cnt$ 了。 #### CF1119H Triple 把 $a$ 异或成 $0$。相当于上一题的二元版本。$F=\prod_i(X+Y\cdot x^{b_i}+Z\cdot x^{c_i})$。 $[x^S]\text{FWT}(F)=\prod_i(X+Y\times (-1)^{S\cap b_i}+Z\times (-1)^{S\cap c_i})$。 依旧考虑求出 $\pm Y\pm Z$ 四种情况的个数。实际上现在 $X,Y,Z$ 都只对最终答案有影响了，求 $cnt$ 时我们不妨将他们都看作 $1$ 和 $0$。 用上题的方法，把 $b_i$ 项依然贡献到 $x^{b_i}$，其余两项忽略，这样就能求出 $cnt(-Y,-Z)+cnt(-Y,+Z)$。同理可对 $c$ 求出 $cnt(-Y,-Z)+cnt(+Y,-Z)$。 考虑 $(-1)^{|b_i|}\times (-1)^{|c_i|}=(-1)^{|b_i\oplus c_i|}$，所以将 $\prod(x^{b_i\oplus c_i})$ 用上题方法求解就能得到 $cnt(-Y,+Z)+cnt(+Y,-Z)$，也就能解出全部 $cnt$ 了。 不难发现这种做法可以扩展到 k-元 的一般情况，复杂度带一个 $2^k$。 #### QOJ#5089. 环覆盖 一个图可环覆盖的充要条件是每个点都是偶度数，也就是若干欧拉图的并。不过直接用前面题的做法难以脱离 $\text{poly}(2^nm)$ 之类的复杂度。 考虑将每条边看作形式幂级数 $x^{\{u,v\}}$，这样偶度图就可以表示为 $[x^\varnothing]F$。 考虑二元 GF 的思想，选 $t$ 条边的答案相当于 $[x^{\varnothing}y^t]\prod(1+x^{\{u_i,v_i\}}y)$。 与上一题类似，根据 FWT 的展开式，只需要枚举 $S$ 并求出 $cnt(S)$ 表示恰有一个端点在 $S$ 中的边数，那么 $[x^S]\text{FWT}(F)=(1-y)^{cnt(S)}(1+y)^{m-cnt(S)}$，后者只有 $O(m)$ 个本质不同的值，在最后一并处理即可。 求 $cnt(S)$，直接高维前缀和是可以的，复杂度带个 $n$。实际上可以从 $S/\text{lowbit}(S)$ 向 $S$ 递推，那么复杂度就是 $O(2^n+\text{poly}(m))$ 的了。（只需要求 $[x^\varnothing]F$，不需要全部 IFWT 回去）。 #### P13275 [NOI2025] 集合 默认乘法是或卷积。 一生之敌。再无话说，请速速动手。 取补集，考虑二元 GF： $$\begin{aligned} G=\prod_S F_S&=\prod_S(1+a_Sx^S+a_Sy^S)\\ \text{FMT}_{x,y}(F_S)&=\sum_{T_x}\sum_{T_y}(1+[S\subseteq T_x]a_S+[S\subseteq T_y]a_S)x^{T_x}y^{T_y}\\ [x^{T_x}y^{T_y}]\text{FMT}_{x,y}(G)&=\prod_S(1+[S\subseteq T_x]a_S+[S\subseteq T_y]a_S)\\ [x^Sy^S]G&=\sum_{T_x\subseteq S}\sum_{T_y\subseteq S}(-1)^{|S/T_x|+|S/T_y|}\prod_{S'}(1+[S'\subseteq T_x]a_{S'}+[S'\subseteq T_y]a_{S'})\\ &=\sum_{T_x\cup T_y\subseteq S}(-1)^{|T_x|+|T_y|}\prod_{S'\subseteq T_x}(1+a_{S'})\prod_{S'\subseteq T_y}(1+a_{S'})\prod_{S'\subseteq T_x\cap T_y}\dfrac{1+2a_{S'}}{(1+a_{S'})^2}\\ ans&=\sum_{T_x, T_y}2^{n-|T_x\cup T_y|}(-1)^{|T_x|+|T_y|}\prod_{S'\subseteq T_x}(1+a_{S'})\prod_{S'\subseteq T_y}(1+a_{S'})\prod_{S'\subseteq T_x\cap T_y}\dfrac{1+2a_{S'}}{(1+a_{S'})^2}\\ &=2^n\sum_{T_x, T_y}2^{|T_x\cap T_y|}(-\dfrac{1}{2})^{|T_x|+|T_y|}\prod_{S'\subseteq T_x}(1+a_{S'})\prod_{S'\subseteq T_y}(1+a_{S'})\prod_{S'\subseteq T_x\cap T_y}\dfrac{1+2a_{S'}}{(1+a_{S'})^2}\\ &=2^n\sum_{T_x, T_y}A(T_x)\times A(T_y)\times B(T_x\cap T_y) \end{aligned}$$ 实际上会存在 $a_{S'}=0$ 的情况，记录一个 $0$ 的个数，对于每个合并到 $T_x\cap T_y$ 的状态，实际上只有 $0$ 取到最小值的项是有用的，所以复杂度不产生变化。 ## 双连通计数 思想仍是逐点牛顿迭代的增量法。 #### LOJ#6730. 边双连通生成子图计数 基于这样一个反演思路：令集合幂级数 $P_i(i\in[0,n])$ 表示只考虑（两端点均）$<i$ 的割边的集合为 $S$ 的子图的方案数（非割边无限制）。那么需求的就是 $P_0$，已知的是 $P_n$（连通图计数）。考虑求 $P_i\to P_{i+1}$ 的增量变换，最后再推导 $P_{i+1}\to P_i$ 的逆变换。 假设现在是 $P_x\to P_{x+1}$，增加了编号为 $x$ 的节点，此时两端点编号最大值为 $x$ 的割边会被考虑进来。 令 $Q_x=[x\not\in S]P_x\cdot \text{coef}(x, S)$ 表示从 $x$ 连接 $S$ 这个块的方案数，$\text{coef}$ 表示满足上述条件的边数。 那么有 $P_{x+1}=P_x\times \exp(Q_x)$，不过对于不含 $x$ 的 $S$ 项其实是 $P_{x+1}=P_x$。 考虑反演，从 $P_{x+1}$ 到 $P_x$。由于上面的特判，不含 $x$ 的项是已知的，所以 $Q$ 是已知的。那么对含 $x$ 的项计算 $P_{x}=\dfrac{P_{x+1}}{\exp(Q_x)}$ 即可。 复杂度是 $n$ 次 $\exp$ 与求逆，为 $O(2^nn^3)$。 #### LOJ#6729. 点双连通生成子图计数 与上一题类似，割边变成了割点。 把所有含 $x$ 的集合拿出来，去掉 $x$ 当作 $Q$。那么 $P_{x+1}$ 的含 $x$ 项即为 $\exp(Q)$。 反演的话直接求个 $\ln$ 即可。 实际上这题也不需要边双连通复杂的思考方式，直接看作按顺序枚举割点并删去即可。 #### LOJ#6719. 「300iq Contest 2」数仙人掌 加强版 其实是上一题的正向版本。我们不知道 $P_n$，但是反而知道 $P_0$ 了（用一个哈密顿 DP 就可以求出）。 同样增量法，钦定每个割点，$\exp$ 合并即可。 #### UOJ#962. 【UR #30】交通管制 上述边双连通的方法是可以边带权的，本题中我们会用到边带常数权的情况，记作 $\text{trans}(F,c)$ 表示每连一条割边就乘上 $c$ 权值。注意这个结果是一个集合幂级数，而不是仅仅 $[x^U]$ 的值。不难发现边双连通计数时用到的反演其实就是 $\text{trans}(F,-1)$。（因为 $(\exp F)^{-1}=\exp(-F)$） 考虑 $\text{type}=2$ 的限制，相当于两个点 $s_i,t_i$ 在边双树的简单路径上至少存在一个 $>1$ 的边双（其实是 $>2$）。 考虑这样的没有 $>1$ 点双的连通块，本质上就是一个生成树计数，令集合 $S$ 的生成树计数为 $f_S$，令 $S$ 的大小 $>1$ 的边双连通子图计数为 $g_S$。 但问题是你直接钦定一个 $f$ 的集合然后与 $g$ 合并是不对的，因为 $f$ 并非是极大的生成树。所以考虑容斥，先做一个 $\text{trans}(f,-1)$，然后带上 $g$ 即可，即 $h=\text{trans}(\text{trans}(f,-1)+g,1)$。 现在考虑 $\text{type}=1$ 的限制，把 $h$ 中不符合连通性的扔掉，然后求一个 $\exp(h')$ 即可。 #### P11567 建造军营 II 不难发现同一个边双的权值（$1$ 或 $2$）是一样的，一个边双边权为 $2$ 当且仅当其在边双树上不被题目的关键路径经过。 考虑刻画极大的 $1$ 连通块，这样的连通块一定由若干边双组成。首先若块内不存在关键点则一定边权不为 $1$，其次若存在一条关键路径没有被完整经过则一定不极大，满足这些条件后，还必须要保证每个边双一定在关键路径上。 用上面的逐点牛顿迭代（增量法）考虑，$P_n$ 就是满足前两个条件的连通块数，$P_0$ 就是需要求的答案，每次钦定若干条割边表示它们不在关键路径上，你发现转移式其实和边双计数是一模一样的，就是 $P_{x+1}=P_x\times \exp(Q_x)$。所以直接得到了 $F=P_0=\text{trans}(P_n,-1)$。 考虑 $2$ 连通块，这个就没有那么多细节了，因为其它的割边也都是权值为 $2$。所以计数出 $G$ 表示每个边双连通块的**权值和**（$2^{|E|}$），且把不存在关键点的 $S$ 都扔掉，那么答案就是 $\text{trans}(F+G,2)$ 了。