生成函数 GF 与集合幂级数

· · 算法·理论

生成函数

建议搭配多项式学习笔记食用。
按照学习顺序排列，有的可能做了少许调整，总之不是按照难度排序的。

下文用 F 表示 OGF，\hat F 表示 EGF，f 表示在 OGF 下这一项的值。

[这是题单喵呜](https://www.luogu.com.cn/training/497380) ## 一些经典数列的 GF $\langle1,1,1\dots\rangle$ 的 OGF：$F=\dfrac1{1-x}$。 Fibonacci 数列的 OGF：$F=\dfrac x{1-x-x^2}$。 卡特兰数的 OGF：$F=\dfrac{1-\sqrt{1-4x}}{2x}$。 $\langle1,1,1\dots\rangle$ 的 EGF：$\hat F=e^x$。 $\langle1,p,p^2\dots\rangle$ 的 EGF：$\hat F=e^{px}$。 ## OGF 与 EGF 的卷积 $\langle a_n\rangle$ 的 OGF 与 $\langle b_n\rangle$ 的 OGF 相乘，结果表示的是 $\langle \sum_{i=0}^na_ib_{n-i}\rangle$ 的 OGF。 $\langle a_n\rangle$ 的 EGF 与 $\langle b_n\rangle$ 的 EGF 相乘，结果表示的是 $\langle \sum_{i=0}^n\binom nia_ib_{n-i}\rangle$ 的 EGF。 以上两点可以根据多项式乘法的定义得到。 换个角度解释，OGF 的卷积就是再做无标号的背包，EGF 的卷积就是再做有标号的背包。 ## EGF 中 exp 的意义 **有标号元素构成的集合的生成集族有多少种情况，或划分为任意个非空子集的总方案数。** 举例： 如果 $n$ 个点带标号生成树的 EGF 是 $\hat F(x)$，那么 $n$ 个点带标号生成森林的 EGF 就是 $\exp\hat F(x)$。 如果 $n$ 个点带标号无向连通图的 EGF 是 $\hat F(x)$，那么 $n$ 个点带标号无向图的 EGF 就是 $\exp\hat F(x)$。 证明：注意到 $\exp\hat F(x)=\sum_{i=0}^{\infty}\frac{\hat F^i(x)}{i!}$。根据上面所说的 EGF 卷积的意义，$\frac1{i!}$ 表示的是这 $i$ 个 $F$ 之间不区分。 ## [集合划分计数](https://www.luogu.com.cn/problem/P5748) 如果不划分，那么方案数显然是 $\langle0,1,1,1\dots\rangle$，所以 EGF 为 $\hat F=e^x-1$。根据上面所述，设答案为 $\hat G$，那么有 $\hat G=e^{\hat F}$。 ## [付公主的背包](https://www.luogu.com.cn/problem/P4389) 放这个题是想说一下欧拉变换。 设当前物品体积为 $v$，那么对应的 OGF 就是 $F=\dfrac1{1-x^v}$，显然答案是所有生成函数的乘积。但是直接做会 T 飞，显然也不能直接上什么分治 NTT 一类的东西。但是这个多项式很厉害，因为他的 $\ln$ 非常简洁，所以我们转化为求所有 $\ln$ 函数的和。 $$ \begin{aligned} \ln F&=G\\ -\ln{(1-x^v)}&=G\\ -\frac{(1-x^v)'}{1-x^v}&=G'\\ \frac{vx^{v-1}}{1-x^v}&=G'\\ \sum_{i\ge0}vx^{vi+v-1}&=G'\\ \sum_{i\ge0}\frac{vx^{vi+v}}{vi+v}&=G\\ \sum_{i\ge1}\frac{x^{vi}}i&=G\\ \end{aligned} $$ 于是，对物体体积去重之后跑这个东西，即可在 $O(n\log n)$ 时间内求出答案 OGF 的 $\ln$ 值，最后再 $\exp$ 回去即可。 ## Euler 变换 $$\mathcal E(F(x))=\prod_{i=1}^{+\infty}\dfrac1{(1-x^i)^{f_i}}$$ **意义：无标号元素构成的集合的生成集族有多少种情况，或划分为任意个非空子集的总方案数。** **有标号情况下的 exp 等价无标号情况下的 euler 变换。** 这个式子可以像上面那样处理，于是可以得到另一个定义式： $$\mathcal E(F(x))=\exp\left(\sum_i\frac{F(x^i)}i\right)$$ 里面是一个调和级数的复杂度，这个显然更利于我们计算。 ## [有标号二分图计数](https://www.luogu.com.cn/problem/P7364) 设二分图的 EGF 为 $\hat F$，二分连通图的 EGF 为 $\hat G$，显然有 $\hat F=e^{\hat G}$。 不过发现 $\hat G$ 也不好算，考虑有什么好算且与二分图有关的东西：二分染色图。设二分染色图为 $\hat H$，那么有 $h_n=\sum\limits_{i=0}^nC_n^i2^{i(n-i)}$。并且发现 $\hat H$ 与 $\hat G$ 之间满足 $\hat H=\sum\dfrac{2^i\hat G^i}{i!}=e^{2\hat G}$。联立最开始的式子可以得到 $\hat F=\sqrt{\hat H}$。 ## [有标号 DAG 计数](https://www.luogu.com.cn/problem/P6295) 设 $F$ 为不要求弱连通的 DAG 数量，问题转化为求 $F$。 其实有点像 DAG 容斥，总的思路是枚举入度为 $0$ 的点。但是因为这里每个点等价，所以不需要枚举子集，只需要枚举个数。$f_n=\sum\limits_{i=1}^nC_n^i(-1)^{i+1}f(n-i)2^{i(n-i)}$。 可以半在线卷积，但是式子列出来发现只需要一次多项式求逆。需要注意这样算出来的是 $F$，我们要的是 $\hat F$，要转化一下。 ## 牛顿迭代 作用：求 $F(x)$ 的零点。 设当前答案为 $t$，过 $t$ 作 $F$ 的切线：$y-F(t)=F'(t)(x-t)$。我们取新的答案为该直线与 $x$ 轴的交点：$t'=t-\dfrac{F(t)}{F'(t)}$。这样做精度会翻倍，体现在多项式中则是有效位数翻倍。 求导时需要注意到底什么是未知数，什么是常量，具体可以见下面例题。 ## 无标号有根树计数 设答案的生成函数为 $F$，有递推式：（可能要稍加思考） $$f_n=[x^{n-1}]\prod_{i=1}^{n-1}\left(\sum_{j=0}x^{ij}\right)^{f_i}=[x^{n-1}]\prod_{i=1}^{n-1}\frac1{(1-x^i)^{f_i}}$$ 其实，如果对上面所讲的 euler 变换足够熟悉，可以一眼看出本题的式子：$F(x)=x\cdot\mathcal E(F(x))=x\cdot\exp\left(\sum\dfrac{F(x^i)}i\right)$。 可以用牛顿迭代做到 $O(n\log n)$，或者分治 NTT 做到 $O(n\log^2n)$，实际效率相差不大。下面介绍牛顿迭代的做法。当然直接做还是不好做，由于 $\ln\left(\dfrac{F(x)}x\right)=\sum\dfrac{F(x^i)}i$，于是对这个东西求零点。而对于右边的和式，注意到只有 $F(x)$ 是变量，当 $i\ge2$ 时，$F(x^i)$ 为常量，换句话说导一下就没了！ $$ \begin{aligned} &\quad F(x)-\frac{\ln(\frac{F(x)}x)-\sum\frac{F(x^i)}i}{\left(\ln(\frac{F(x)}x)-\sum\frac{F(x^i)}i\right)'}\\ &=F(x)-\frac{\ln(\frac{F(x)}x)-\sum\frac{F(x^i)}i}{\left(\ln(\frac{F(x)}x)-F(x)\right)'}\\ &=F(x)-\frac{\ln(\frac{F(x)}x)-\sum\frac{F(x^i)}i}{\dfrac{\frac1x}{\frac{F(x)}x}-1}\\ \end{aligned} $$ 需要注意的是 $f_0=0$，所以分母只能是 $\frac{f(x)}x$。 但是按照这个式子做是**错误的**！（真的很难找，本人找错花了 $3\rm{days}$）我们一直说，牛顿迭代可以使精度翻倍，但是注意这里，我们多次使用了 $\frac{F(x)}x$，他的精度并不是 $\bmod x^n$，而是 $\bmod x^{n-1}$。这会导致倍增的时候出问题。 怎么修锅？只需要对 $G(x)=\frac{F(x)}x$ 牛顿迭代就好了。 $$G(x)-\frac{\ln(G(x))-\sum\frac{F(x^i)}i}{\frac1{G(x)}-x}$$ 常数巨大。 ## [无标号无根树计数](https://www.luogu.com.cn/problem/P5900) 考虑转化为有根树——钦定树根为树的重心。设有根树的生成函数为 $F$。稍加思考可以发现，计算一个点是重心不太容易，不过计算一个点不是重心可太方便了，把那个 $size>\frac n2$ 的子树拿出来就好。故而答案为： $$f_n-\sum_{i=\lfloor\frac n2\rfloor+1}^{n-1}f_if_{n-i}$$ 这样就结束了……吗？ 将重心当作树根，需要考虑一个特殊情况——双重心！故而在 $n$ 为偶数时，答案需要额外减去 $\Large\binom{f_{\frac n2}}2$。 ## [烷基计数](https://loj.ac/p/6538) 哇偶，是化学！（感觉比上面那道有根树计数简单，只是平凡的牛顿迭代） 英语小知识：alkyl。 显然原问题等价于 $n$ 个点的无标号有根树计数，且要求每个点的儿子个数不超过 $3$。 由 burnside：$F(x)=\frac x6(F^3(x)+3F(x)F(x^2)+2F(x^3))+1$。显然可以施半在线卷积做到 $O(n\log^2 n)$，不过这里有更加优秀的单 $O(\log n)$ 做法——牛顿迭代。 我们想求解 $\frac x6(F^3(x)+3F(x)F(x^2)+2F(x^3))+1-F(x)$ 的零点。注意到，当 $\bmod x^n$ 变为 $\bmod x^{2n}$ 时，$F(x^2),F(x^3)$ 的值我们是知道的，换句话说未知数只有 $F(x)$，这点在求导时需要注意。 $$ \begin{aligned} G(x)&=F(x)-\frac{\frac x6(F^3(x)+3F(x)F(x^2)+2F(x^3))+1-F(x)}{(\frac x6(F^3(x)+3F(x)F(x^2)+2F(x^3))+1-F(x))'}\pmod{x^{2n}}\\ &=F(x)-\frac{\frac x6(F^3(x)+3F(x)F(x^2)+2F(x^3))+1-F(x)}{\frac x6(3F^2(x)+3F(x^2))-1}\\ &=\frac{\frac x3(F^3(x)-F(x^3))-1}{\frac x2(F^2(x)+F(x^2))-1}\\ \end{aligned} $$ 倍增即可做到 $O(n\log n)$。 ## [烯烃计数](https://www.luogu.com.cn/problem/P6597) 英语小知识：alkene。 设烯烃的生成函数为 $F$。由于烯烃拥有唯一一个碳碳双键，非常自然的想法是依赖这个双键计数。而只考虑一部分，这是一棵所有点的叶子不超过 $3$，且根节点叶子不超过 $2$ 的有根树，设他的生成函数为 $G$。不难想到 $G$ 应该和我们上面算的烷基有点关系，我们再设烷基为 $H$。 由 burnside：$G=x\dfrac{H^2(x)+H(x^2)}2,F=\dfrac{G^2(x)+G(x^2)}2$。 ## [烷烃计数](https://www.luogu.com.cn/problem/P6598) 英语小知识：alkane。 采用无根树的惯用手法，钦定重心为根节点，设烷基的生成函数为 $F$，则答案为 $$tot-\sum_{i=\lfloor\frac n2\rfloor+1}^{n-1}f_if_{n-i}-[2\mid n]\binom{f_{\frac n2}}2$$ 显然这里的 $tot\ne f_n$，他可以有 $4$ 个儿子。由 bunside 可得： $$tot=x\frac{F^4(x)+6F^2(x)F(x^2)+8F(x)F(x^3)+3F^2(x^2)+6F(x^4)}{24}$$ ## 泰勒展开 函数 $f(x)$ 在 $a$ 处的泰勒展开： $$ \begin{aligned} f(x)&=f(a)+f'(a)(x-a)+\frac{f''(a)}2(x-a)^2+\frac{f'''(a)}6(x-a)^3+\dots\\ &=\sum_{i=0}^{\infty}\frac{f^{(i)}(a)}{i!}(x-a)^i \end{aligned} $$ 显然，展开的项数越多，右式就越逼近左式。取 $a=0$ 常常有不错的效果，故而此时有另一个名字：**麦克劳林展开**。 泰勒展开给出了将任意一个函数化为多项式形式的方法。此方法主要运用于将封闭形式转化回数列的通项。 eg.：$e^x=\sum\dfrac{_{x=0}\mid(e^x)^{(i)}}{i!}x^i=\sum\dfrac{x^i}{i!}$。 ## 拉格朗日反演 注：这个东西涉及到多项式复合的**定义**，并不需要真的求解，无需害怕。 **多项式复合逆**：如果有 $F(G(x))=x$，容易证明 $G(F(x))=x$，我们称他们互为复合逆。 注：这里指的是形式幂级数的复合逆。如果真的是狭义的多项式复合逆的话，只有一次函数才存在。 若 $F,G$ 互为复合逆，$F=\sum f_ix^i,G=\sum g_ix^i$，且满足 $f_0=g_0=0,f_1\ne0,g_1\ne0$。 $$ \begin{aligned} \sum g_iF^i&=x\\ \sum g_i\times iF^{i-1}F'&=1&&\text{(对两边求导)}\\ [x^{-1}]\sum ig_i\times F^{i-n-1}F'&=[x^{-1}]\frac1{F^n}&&\text{(同 }\div F^n\text{,提取 -1 次项的系数)}\\ \sum ig_i\times[x^{-1}]F^{i-n-1}F'&=[x^{-1}]\frac1{F^n}\\ \end{aligned} $$ 其中 $[x^{-1}]F^{i-n-1}F'$ 可以用形式洛朗级数的一个结论：$[x^{-1}]F^kF'=[k=-1]$。于是，上述求和式中，只有 $i=n$ 时存在贡献： $$ \begin{aligned} ng_n&=[x^{-1}]\frac1{F^n}\\ [x^n]G&=\frac1n\cdot[x^{-1}]\frac1{F^n}\\ [x^n]G&=\frac1n\cdot[x^{n-1}]\left(\frac xF\right)^n \end{aligned} $$ 同样的，有 $[x^n]F=\dfrac1n\cdot[x^{n-1}]\left(\dfrac xG\right)^n$，这便是拉格朗日反演公式。（这里把 $[x^{-1}]$ 变为 $[x^{n-1}]$ 的一大原因是，$F,G$ 均不存在逆，而 $\frac xG$ 的常数项有值） 当然，$F(G(x))=x$ 的条件较为苛刻，OI 中常见的是 $F(G(x))=H(x)$。于是出现了**扩展拉格朗日反演**：$[x^n]F=\dfrac1n\cdot[x^{n-1}]H'\left(\dfrac xG\right)^n$。 ## [边双连通图计数](https://www.luogu.com.cn/problem/P5828) ### Solution1 %%% zky 的不用拉反做法。 设一般连通图的生成函数为 $F$，显然 $F$ 可以通过对任意图的生成函数求 $\ln$ 得到。设边双连通图的生成函数为 $G$。 发现 $G$ 并不好直接求得，考虑容斥： $$f_n=\sum_{i=1}^ng_i\sum_{x_1+x_2\dots+x_k=n-i\texttt{(有标号)}}\left(\prod_{j=1}^kf_{x_j}x_ji\right)$$ 其中，第一个求和是在枚举包含 $1$ 号点的边双联通集合大小，第二个求和是在枚举这个集合与其他点的连边。 然后……就倒闭了，因为有 $i^k$ 的缘故，后面的乘积形式很难做，并不能直接 $\exp(\hat H)$，至少也是 $\exp(i\hat H)$。 换一个容斥的角度，直接枚举各个边双联通的构成：（这里需要使用 prufer 相关结论） $$f_n=\sum_{x_1+x_2\dots+x_i=n\texttt{(有标号)}}\left(\frac1{n^2}\times\prod_{j=1}^inx_jg_{x_j}\right)$$ 对右式使用容斥（现在知道 $g$ 可以求 $f$，自然可以通过 $f$ 求 $g$），则容斥系数为 $-\frac1{n^2}\prod(-nx_j)$。注意为什么乘积里面也有一个负号，这是因为我们是对边双联通分量个数容斥的。 设 $h_i=-nif_i$，那么有 $[x^n]\hat G=[x^n]-\frac1{n^2}\exp(\hat H)$。 ### Solution2 我们说刚才说 $\exp(i\hat H)$ 难做，不过现在我们会拉格朗日反演了，再尝试一下。 $F,G$ 的定义同上，我们设 $h_i=if_i$，即有根连通无向图的数量，那么有： $$\hat H=\sum\frac{g_i\exp(i\hat H)}{i!}x^i=\hat G(x\exp(\hat H))$$ 令 $\hat P=x\exp(\hat H)$，则 $\hat G(\hat P)=\hat H$，标准的拉反形式，且 $\hat H,\hat P$ 均可以简单求得。 ## [点双连通图计数](https://www.luogu.com.cn/problem/P5827) 明确点双的特点：每个点至少在一个点双中，且各个点双大小不少于 $2$。因此 $n=1$ 需要特判。 设 $F$ 表示**有根**无向连通图（即上一道题的 $H$），$G$ 表示点双联通图。借助圆方树，我们考虑进行 DP。设 $h_i$ 表示一个**方点为根**的子树，共有 $i$ 个圆点，对应的方案数（为了更好算，算上方点的父亲，不过不计入 $i$ 里面）。 $$ h_n=\sum_{i=1}^ng_{i+1}\cdot[x^n]{\hat F^i}\\ f_n=n\times[x^{n-1}]\exp(\hat H)\times(n-1)! $$ 着重说一下第二个式子：$f$ 的定义是“有根”，所以右式需要先枚举根，也就是乘 $n$，然后后面提取系数的部分是无根的。 先看上面那个： $$ H=\sum g_{i+1}\hat F^i\\ \hat H=\sum\frac{g_{i+1}\hat F^i}{i!}\\ \hat H=\hat G'(\hat F) $$ 将其带入下面的式子： $$ [x^n]\hat F=[x^{n-1}]\exp(\hat H)\\ \frac{\hat F}x=\exp(\hat G'(\hat F))\\ \ln(\frac{\hat F}x)=\hat G'(\hat F) $$ 令 $P=\ln(\frac{\hat F}x)$，由拉格朗日反演：$[x^n]\hat G'=\frac1n[x^{n-1}]P'\exp(-nP)$。 最终的答案为 $g_n=[x^{n-1}]\hat G'\times(n-1)!$。 ## [第二类斯特林数·列](https://www.luogu.com.cn/problem/P5396) 第二类·行是 NTT 板子，此处略过。 设 $F$ 表示单个盒子的方案数，容易得到 $\hat F=e^x-1$（减 $1$ 是因为不能为空）。为了体现在同一个集合，我们不妨给集合标号，那么从单个盒子到 $k$ 个盒子，其实就是之前说的有标号背包，故答案的 EGF 为 $\frac{\hat F^k}{k!}$（这里除 $k!$ 是因为原本不区分各集合）。 command_block 大佬有一个基于倍增的单 $\log$ 做法，相比这里的快速幂常数更小。但是就理解运用来说，显然是 $\exp$ 更简单直接。 ## [第一类斯特林数·列](https://www.luogu.com.cn/problem/P5409) 同样的，对集合进行标号处理，和上面那道几乎一致。唯一不同的是，$\hat F=\sum_{i=1}^{+\infty}\frac{(i-1)!x^i}{i!}=\sum_{i=1}^{+\infty}\frac{x^i}i$。 ## [第一类斯特林数·行](https://www.luogu.com.cn/problem/P5408) 回忆当时做第二类·行，使用了斯特林反演，不难猜测这里可能也要联立一个等式。可能需要一些上升下降幂的前置知识： $$x^{\overline n}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i\qquad x^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i}$$ > proof：（以第一个为例） > 归纳证明。当 $n=0$ 时，命题显然成立。 > 当 $n-1$ 成立时，考虑递推公式 $\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}$。命题右侧显然是第 $n$ 行的 OGF，设为 $F_n$，由递推公式，容易得到 $F_n=xF_{n-1}+(n-1)F_{n-1}=(x+n-1)F_{n-1}=(x+n-1)x^{\overline{n-1}}=x^{\overline n}$，命题成立。 > $\square

因为可以反演，所以上面的转化关系是双向的，总之要记住上升幂对应第一类斯特林数，下降幂对应第二类斯特林数。

于是现在的问题变为如何求解上升幂。当然你可以分治 NTT 碾过去，我们这里主要讨论单 \log 的倍增做法。
由于 x^{\overline{2n}}=x^{\overline n}(x+n)^{\overline n}，所以只需要根据 f(x) 快速求出 f(x+k) 就行。

\begin{aligned} &\quad f(x+k)\\ &=\sum_{i=0}^n f_i(x+k)^i\\ &=\sum_{i=0}^n f_i\sum_{j=0}^i\binom ijx^jk^{i-j}\\ &=\sum_{i=0}^n f_ii!\sum_{j=0}^i\frac{x^j}{j!}\frac{k^{i-j}}{(i-j)!}\\ &=\sum_{j=0}^n x^j\frac1{j!}\sum_{i=j}^nf_ii!\frac{k^{i-j}}{(i-j)!}\\ \end{aligned}

直接卷积即可。

循环卷积

我们想让 f_0 的前一项变为 f_n。做法比较典：模上 (x^{n+1}-1) 即可。
如果是单次多项式乘法，只需要额外执行一次多项式取模即可。不过通常循环卷积不会只执行一遍，也就是说常会出现多项式快速幂。显然不能大力 \ln，当然可以倍增 + NTT 做到 O(n\log^2n)，事实上，对于普通的问题，到这里就无法优化了。

这里要引入另一个优化：如果我们需要 \bmod(x^{2^k}-1)，存在更快的单 \log 算法。应用是 https://atcoder.jp/contests/fps-24/tasks/fps_24_r。
考虑 NTT 的过程，当我们把一个 n 次多项式与 m 次多项式相乘时，结果是 n+m 次多项式。因为 DFT 要求必须补全到 2 的幂次，我们一般取最小的满足 n+m<2^{bit} 的值。那么，如果我们强行令 bit=k 会发生什么呢？答案是，无法区分 g^{2^k}=1，其中 g 为 2^k 次单位根，当然在整数域下是原根的幂次。换句话说，会把 x^0 与 x^{2^k} 当做一个东西——这不正是我们想要的吗？
于是，强行把 NTT 的项数开到 2^k，即为对 (x^{2^k}-1) 取模的结果。先做一遍 DFT，将点值快速幂一下，然后再 IDFT 即为所求。

集合幂级数

如今的 CNOI 可以说几乎看不到多项式题，主要是多项式这类科技在考试时实在不方便出现，光是敲模板就要耗费大量时间。而且多项式本身算一个较为独立的内容，与其他知识点的结合少之又少。但是，与多项式强相关的知识点，无需冗长模板的集合幂级数，则特别受喜爱，在如今的 CNOI 屡见不鲜。因此，掌握集合幂级数的相关技巧十分重要。
一般来说，用集合幂级数科技可以在 O(2^npoly(n)) 解决的题目，同样可以在不使用科技的情况下在 O(3^npoly(n)) 内解决。

推荐阅读：APIO2025 中 cxy 讲的集合幂级数课件。

我们用 F\times G 表示两个集合幂级数的无交并，即子集卷积的结果。下文中集合幂级数的 f_0 均表示 f_{\varnothing}，需要注意的是，在集合幂级数中一般都有 f_{0}=0\operatorname{or}1，接下来的运算中可能会用到该性质。
注意区分“点子集”与“边子集”，不加说明的话，认为下文的“子集”指“点子集”。事实上，子图计数问题中，对点子集计数的学术价值不大，因为我们可以直接 O(2^n) 枚举集合之后 poly(n) 判定。所以，子图计数通常都指边子图计数。
有关集合幂级数的编号均为 0-index。

集合幂级数下的多项式全家桶

最基础的 FWT 和子集卷积属于基础内容，在多项式学习笔记中。

这里只考虑三个：\operatorname{inv}(F),\ln(F),\exp(F)。显然，我们不可能像普通多项式那样，根据求导、牛顿迭代之类的科技求解。于是，我们只能将需要求解的函数展开成为非封闭的无限项数求和形式，然后类似多项式复合那样带入求解。

\frac1{1-x}=\sum_{i=0}^{+\infty}x^i\\\ln(1-x)=-\sum_{i=1}^{+\infty}\frac{x^i}i\\\exp(x)=\sum_{i=0}^{+\infty}\frac{x^i}{i!}\\

用麦克劳林展开即可得到。

将上述展开式改为我们想要的函数：

\operatorname{inv}(F)=\sum_{i=0}^{+\infty}(1-F)^i\\\ln(F)=-\sum_{i=1}^{+\infty}\frac{(1-F)^i}i\\\exp(F)=\sum_{i=0}^{+\infty}\frac{F^i}{i!}\\

当然，这里有太多的多项式乘法，考虑直接对点值做运算。先按照子集卷积那样跑一遍 \operatorname{FMT}(F)，将 F_{*,s} 做上面的运算得到新幂级数 G_{*,s}，则 \operatorname{IFMT}(G) 即为所求。当然，这里指的是 [x^{pc(i)}]g_i，因为 F,G 的每一项都是一个占位多项式。

有一个需要解决的问题是无限项数求和。注意到，\operatorname{inv}(F) 和 \ln(F) 都要求 f_0=1^{(*)}，而 \exp(F) 要求 f_0=0，于是等式右侧 i 次方后的最小次数也为 i，即 i>n 时的所有值都取不到（因为此时 pc(i)>n）。求和只需求到 n 即可，包括做多项式乘法的时候也只需要保留次数不超过 n 的项。
注^{(*)}：在模板题中，求逆并没有要求 f_0=1，可以理解为先提出一个 f_0 的系数再运算。

FWT 部分不是复杂度瓶颈，问题在于每次对 F_{*,s} 进行多项式运算，容易做到 O(2^nn^3)。但这并不够优秀，通过上面的定义式求解显得太不聪明了，因为每次对一个形式幂级数做多项式基本操作可以做到 n^2，于是总复杂度为 O(2^nn^2)。

同样的，exp 与 ln 具有与普通多项式相同的组合意义。例如，集合幂级数下的 exp 同样可以代表划分为任意个非空子集的总方案数。于是上面的一些例题，例如连通图计数与二分图计数的子图计数版本，可以使用相同的方法去做，换一下初值以及函数的实现即可。这里不再展开。

多项式复合集合幂级数

既然特殊 FPS 复合 SPS 可以在 O(2^nn^2) 求解，自然会继续思考是否任意 FPS 复合 SPS 都可以在同样的复杂度求解。答案是肯定的。当然，这里要求 SPS 的常数项为 0，否则 F^i 不会收敛到 0。
首先要明确的是，如果想在之前做法的基础上继续扩展，则我们需要找到 O(n^2) 求解任意多项式复合的算法。这里不考虑传统复合的 O((n\log n)^{1.5}) 与新复合的 O(n\log^2n)，这纯是科技内容，而且其大常数在这里并不实用。而如果想要 O(n^2) 递推求解任意多项式复合，似乎并不容易。因此，我们需要一个与上述做法截然不同的新做法。

从组合意义的角度入手。[x^S]F^k 的组合意义是，把 S 拆分为 k 个非空子集 S=T_1+T_2+\dots+T_k 的权值之和，加法表示无交并，其中单种拆分方式的权值为 \prod f_{T_i}。这个东西不太方便我们 DP，于是令拆分是无序的，最后带一个 k! 的系数即可，而无序拆分的话就可以钦定 S 的最高位必选。
从小到大枚举 T 的最高位，设 [x^S]H_{i,j} 表示考虑了最高位 <i 的所有 T，这些 T 是 S 的拆分，还需要拆出 j 个 T。初值为 h_{0,i,0}=g_i\times i!，答案为 H_{n,0}。转移其实也不难：

看上去复杂度是爆炸的，因为每轮转移都要做子集卷积。但是注意到每轮的状态数并不是 2^n 的，因为 H_{i,j} 只能由 \max T<i 的 T 拼起来，于是实际项数只有 2^i。计算一下时间复杂度为 \sum_{i=0}^{n-1}(n-i)2^ii^2=2^{n+1}(n^2-6n+13)-6n-26=O(2^nn^2)，空间方面不需要开 i 那一维，为 O(2^nn)。

另：使用类似的方法，可以在同样的时间复杂度解决经典的 [x^U]F^k 问题。具体来说，这个问题形如 f_0=0，需要对于所有 k 求解 [x^U]F^k，U 表示全集。做法大概是将上述过程倒序，将加入 \max S=i 的集合改为删去 \max S=i 的集合。一个经典的应用是求解色多项式。

DAG 容斥

考虑如何对于 DAG 计数，每次可以删去一个入度为 0 的点，直到把整个图删空。对这个删除过程计数，但这样的话会算重，即如果某个时刻有多个入度为 0 的点，我们会算多次。考虑容斥，改为每次枚举一个入度为 0 的点集 S，容斥系数为 (-1)^{|S|+1}。

模板题是 AT_abc306_h Balance Scale，在定向的基础上多了相等，不过这部分并不困难。

例题：P10221 [省选联考 2024] 重塑时光。

强连通生成子图计数

直接对强连通生成子图计数是困难的，考虑类似 DAG 计数一样去容斥。如果一个图不是 scc 的话，那么缩点过后就是一个 DAG，套用上面的 DAG 容斥即可。需要额外求一下，将集合 S 划分成若干 scc，且不同的 scc 之间没有连边的方案数。

可惜的是，该问题目前只能在 O(3^n) 时间复杂度求解，难以做到 O(2^npoly(n) )。

例题：P11834 [省选联考 2025] 岁月。

边双连通生成子图计数

考虑另一个问题（下文称为 A 问题）：给原图的所有点子集 S\subseteq U 一个权重 a_S，定义一张连通图（也不能有孤点）的权值为其所有边双的 \prod a，非连通图的权值为 0。以及不知道哪来的，反正我们知道每一个点子集 S 中的边双连通子图数量为 b_S。我们要求的是 U 中所有边子集的权值之和。
考虑对割边 DP。具体的，我们令 F_i 为一个集合幂级数，其中的 f_{i,S} 表示点集 S 的所有满足割边两端点的编号不超过 i 的边子集的权值之和。这个状态定义是解决该问题的关键，因为最开始我们只知道边双的信息，于是需要一点点的加入割边。显然，f_{0,S}=a_Sb_S，所求即为 f_{n,U}。

定义一条割边 a\leftrightarrow b 的编号为 \max(a,b)。从 F_{i-1} 到 F_i 相当于放宽了限制，允许出现所有编号为 i 的割边。于是一个自然的想法是，求解 F_i 相当于首先断掉所有编号为 i 的割边，划归为若干连通块在 F_{i-1} 下的值。
大致思路就是上文所述，接下来是具体讨论。显然，如果 i\notin S，则 f_{i,S}=f_{i-1,S}。对于 i\in S，假设其划分为 S=P+T_1+T_2+\dots+T_k，这里的加法表示无交并，其中 i\in P，T 之间无序。对于这种划分，其贡献的权值为 f_{i-1,P}\times\prod\limits_{j=1}^kf_{i-1,T_j}\times\left(\sum\limits_{u\in T_j,u<i}[edge(u,i)]\right)，其中 [edge(u,i)] 表示 u,i 之间是否有连边。其含义是容易理解的，即每一个集合会贡献 f_{i-1,T_j} 的权值，再乘上 i 与 T_j 之间存在编号为 i 的割边方案。
于是，令 g_{i-1,S}=f_{i-1,S}\left(\sum\limits_{u\in S,u<i}[edge(u,i)]\right)，其中 i\notin S。那么有 F_i=F_{i-1}\times\exp(G_{i-1})，这里的定义域为包含 i 的项。至此，我们在 O(2^nn^3) 时间复杂度解决了 A 问题，称上述操作为一次正向的“边双连通-连通变换”。

回到原问题，其实我们认为与 A 问题本质相同。令 a_S=1，那么 F_n 表示连通边子集的数量，可以在 O(2^nn^2) 求得，最终所求即为 b_U=f_{0,U}。那么我们只需解决根据 F_i 求 F_{i-1} 的问题，也就是反向的“边双连通-连通变换”。
如果 i\notin S，则 f_{i-1,S}=f_{i,S}，于是 G_{i-1} 我们也是可以算的。对于 i\in S，有 F_{i-1}=F_i\times\exp^{-1}(G_{i-1})=F_i\times\exp(-G_{i-1})。因此，原问题我们同样在 O(2^nn^3) 复杂度解决了。

实现的时候有一个 \frac12 常数的技巧，即每轮跑连通变换的时候，只把不包含 i 的项拿出来跑，总项数就是 2^{n-1} 的。

例题：P11567 建造军营 II。

点双连通生成子图计数

我们尝试仿照上面的方法，写出“点双连通-连通变换”。需要注意的是，同一个点可以在多个点双中。
考虑上面 A 问题的点双版本。如果 i\notin S，则 f_{i,S}=f_{i-1,S}。对于 i\in S，假设其划分为 S=\{i\}+T_1+T_2+\dots+T_k，这里的加法表示无交并，T 之间无序，表示把 i 删掉形成的若干连通块。对于这种划分，其贡献的权值为 \prod\limits_{j=1}^kf_{i-1,T_j\cup\{i\}}，注意这里的 \cup\{i\} 可能需要稍加思考其含义。可以发现，这个递推式比起刚刚的边双计数要更加简洁。令 g_{i-1,S}=f_{i-1,S\cup\{i\}}，其中 i\notin S。那么有 F_i=x^{\{i\}}\exp(G_{i-1})，定义域为包含 i 的项。至此，我们在 O(2^nn^3) 时间复杂度解决了点双版本的 A 问题，称上述操作为一次正向的“点双连通-连通变换”。

回到原问题，仍然有 F_n 表示连通边子图的数量，所求为 b_{U}=f_{0,U}。如果 i\notin S，则 f_{i-1,S}=f_{i,S}。反之，根据 G_{i-1}=\ln\left(\dfrac{F_i}{x^{\{i\}}}\right) 我们可以解出 G_{i-1}，然后有 f_{i-1,S}=g_{i-1,S-\{i\}}。因此，反向的“点双连通-连通变换”我们同样在 O(2^nn^3) 复杂度解决了。

因为没有子集卷积操作，常数比边双小很多，代码也更好写。
需要特判 n=1。

子图容斥的容斥系数

推荐阅读：集合划分容斥的容斥系数。

子图容斥大多属于集合划分容斥，其容斥系数常常难以直接计算。特别是在图上，图的形态一般会影响容斥系数。这时，类比普通容斥那样直接写出容斥系数的通式往往并不可取。
换一个角度看问题，容斥系数的本质是，每种情况会算多遍，每一次的容斥系数组合起来使我们最后想要的系数。也就是说，我们可以用容斥系数表示出我们想要的系数，于是用解方程的思想，把容斥系数解出来即可。

少项式集合幂级数的 FWT

推荐阅读：一种快速计算多个少项式集合幂级数异或卷积的方法。
听说 le0n 今年的集训队论文也是这方面的，而且更加厉害，可以期待一下。

这里的 FWT 指的是异或卷积，少项式指的是只有 O(1) 个位置有值的集合幂级数，通常为 2\sim3 个。没有上面的博客这么难，博客的内容扩展性更强。

首先回到 FWT 的定义式，记 i\circ j 表示 |i\cap j| 的奇偶性，有性质 (i\oplus j)\circ k=(i\circ k)\oplus(j\circ k)。再记 G=FWT(F)，那么 g_s=\sum\limits_{i\circ s=0}f_i-\sum\limits_{i\circ s=1}f_i=\sum\limits_{i}f_i\times(-1)^{i\circ s}。这部分不太会的建议去看 wiki。
根据定义，可以写出另一个性质：[x^i]FWT(F\cdot x^k)=[x^i]FWT(F)\times(-1)^{i\circ k}，证明的话可以带入上面的定义式。这个性质在实际应用中非常方便，因为常常可以通过这个方法把少项式的某一项平移到 x^{\varnothing}。

分类为两种：\prod(a+bx^{c_i}) 和 \prod(a_i+b_ix^{c_i})。第一种算是特化，存在完全不同的简单处理方式，所以单独拿出来。

\prod(a+bx^{c_i}) 型

变形一下，等价于对每一个集合 s，求 \prod[x^s]FWT(a+bx^{c_i})=\prod(a+b\times(-1)^{s\circ c_i})。注意到每一项的贡献要么是 a+b，要么是 a-b，于是可以写作 (a+b)^{\#[s\circ c_i=0]}(a-b)^{\#[s\circ c_i=1]}。
但是 \#[s\circ c_i=0] 与 \#[s\circ c_i=1] 单独一个仍然难做。换个角度，显然二者的和是 n，而二者的差可以用一次 FWT 求得。具体来说，定义集合幂级数 F，满足 f_{c_i}=1，那么 [x^s]FWT(F)=\#[s\circ c_i=0]-\#[s\circ c_i=1]。解二元一次方程组即可。

这个做法显然可以扩展到多元，即少项式的项数可以变多一点。此时往往需要解一个多元一次方程组，比较复杂，故而该做法适用于项数比较少的时候。

例题：uoj310 黎明前的巧克力，CF1119H Triple。

\prod(a_i+b_ix^{c_i}) 型

同样先变形，改为 \prod(a_i+b_i\times(-1)^{s\circ c_i})。我们不能像刚才那样写成求个数的形式了，考虑直接把 a_i,b_i 带入到 FWT 的过程中计算。类似于上面那样，我们知道这一项的贡献只能是 a_i+b_i 或者 a_i-b_i，于是维护一个二元组 (p=a_i+b_i,q=a_i-b_i)。
当 FWT 做到第 i 位的时候，设 f_s=(p_1,q_1),f_{s+2^i}=(p_2,q_2)，那么我们的变换应为 f_s\gets(p_1p_2,q_1q_2),f_{s+2^i}\gets(p_1q_2,q_1p_2)，原因的话可以考虑该次变换对 s\circ c_i 造成的影响。最后的答案是 f_s 的 p 项。

例题：CF2096H Wonderful XOR Problem。