多项式与生成函数
前言
经过一段时间的学习，感觉生成函数主要还是用来优化计数 dp 的，比如你看到一个卷积形式就要想到分治 NTT，看到一个奇怪的图计数或者序列计数就要想到把他的生成函数列出来…
多项式前置知识
NTT
不打算再学一遍了.
多项式求逆
$F(x)\equiv F_0(x)\pmod {x^{n/2}}$
$F^2(x)-2F_0(x)F(x)+F_0^2(x)\pmod {x^n}$
两边同时乘 $G$
$F\equiv2F_0-F_0^2G$
多项式牛顿迭代
直接放结论。
$F=F_0-\frac {G(F_0)} {G’(F_0)}$
多项式开根
令 $H(F(x))=G^2(x)-F(x)$
有 $F\equiv F_0-\frac{G^2-F_0}{2G}\equiv G/2+F_0/2G$
多项式求 ln
两边导，再积分
$\int G’(x)/G(x)=F(x)$
于是求导求逆积分即可。
多项式 exp
变形，令 $H(F)=ln(F)-G$
$F=F_0-(ln(F)-G)F_0=(1-ln(F_0)+G)F_0$
多项式带余除法
$A=BC+R$
$A^T\equiv B^TC^T\pmod {x^{n-m+1}}$
多项式快速幂
$G^k=\exp(k\ln G)$
多项式与递推数列的转化
多项式求逆
考虑递推 $F(x)G(x)=1$ 这个柿子，我们把他按系数打开可以得到结论。
$\sum_{i=0}^n F[i]G[n-i]=[n=1]$
这里有一个套路是拆最高次项，可以得到
$\sum_{i=0}^{n-1}F[i]G[n-i]+F[n]G[0]=[n=1]$
$F[n]=[n=1]/G[0]+\sum_{i=0}^{n-1}F[i]G[n-i]/G[0]$
你发现这个东西当 $G[0]=1$ 的时候正好是分治 NTT ！
这启发我们最简单的分治 NTT 等价于一个求逆。
多项式exp
考虑如下等式
$G’F=F’$
$\sum_{i=0}^nG’[i]F[n-i]=F’[n]$
我们考虑求导之后函数的第 $i$ 项就是原函数第 $i+1$ 项再乘上 $(i+1)$
于是
$\sum_{i=0}^n(i+1)G[i+1]F[n-i]=Fn+1$
你发现可以直接递推了。
多项式求 ln
其实是一样的东西。
$\sum_{i=0}^n(i+1)F[i+1]G[n-i]=Gn+1$
$\sum_{i=0}^{n-1}(i+1)F[i+1]G[n-i]+(n+1)F[n+1]G[0]=Gn+1$
你发现又可以直接递推了。
多项式快速幂
这个稍微麻烦一点，假设 $G$ 是一个 $m$ 次多项式。
$G^k=F$
求导
$kG^{k-1}G’=F’$
考虑我们需要用 $F$ 表示 $F$ 自己。
两边同时乘 $G$
$kFG’=F’G$
接下来大力提取系数就可以做了，这里略。
总结一下，一些生成函数的组合可以表示成递推的形式，而递推也同样可以表示成多项式的形式，二者是对偶的。
生成函数
简介
生成函数就是 $G(x)$ 长相的形式幂级数，满足多项式的一切，其中的系数是一个序列。
序列 $<1,1,1,1,\dots >$ 的生成函数：
序列 $<1,2,3,4,5,\dots >$ 的生成函数：（把上面那个玩意求导）
序列 $<\binom {n}{0},\binom{n}{1},\dots >$ 的生成函数：（根据二项式定理）
序列 $<\binom {n+0}{0},\binom{n+1}{1},\dots >$ 的生成函数：（根据牛顿二项式定理）
以上是一些常见的生成函数。
斐波那契生成函数
对两边同时取生成函数
解出来 $F=\frac {1}{1-x-x^2}$
考虑把这个玩意表示成我们已知的生成函数，通过裂项可以得到
$F=\frac {a}{1-p_0x}+\frac {b}{1-p_1x}$
把这个东西解出来就可以了，之后两边同时取系数就可以得到通项公式。
$f_n=\frac {1}{\sqrt 5}((\frac {1+\sqrt 5} 2)^n-(\frac {1-\sqrt 5} 2)^n)$
OGF
这两个东西是用来解决一些组合计数问题的技术。
其中 OGF 和普通生成函数类似，都是形如 $G(x)=\sum_{i=0}^nG[i]x^i$ 的生成函数，其中 $G[i]$ 是某一个问题的规模为 $i$ 的答案。
考虑两个 OGF 的卷积运算。
$(f*g)[n]=\sum_{i=0}^nf[i]g[n-i]$
这个东西本质上是个背包，也就是我从 $f$ 中选 i 件有 $f[i]$ 种方案，从 $g$ 中选 $i$ 件有 $g[i]$ 种方案，现在我从 $f,g$ 中同时选 $n$ 个的方案是刚才那么多。
也就是说 $f,g$ 在这里是地位相同的，你选这么多我选这么多，相当于装水，你装几升我装几升，顺序是看不出来的。
具体地，我们有两个 EGF 相乘的组合意义是用两种方式共选出某一数量的带标号元素的方案数。
考虑 $F^n$ 的实际含义，是以固定的方式取走 $n$ 个元素的方案数，有无标号根据 EGF 和 OGF 决定，特别地，这个取走是有顺序的，第一次一个第二次两个和第二次两个第一次一个算两种方案。
upd:更进一步
令 OGF $A(x),B(x)$ 分别为两个无标号组合类 $S,T$，其中大小为 $i$ 的对象一共有 $a_i,b_i$ 个，设 OGF 为 $C(x)$ 的无标号组合类 $R$ 满足：
每个对象是 $S$ 或 $T$ 中的一个，有 $C=A+B$。
每个对象的元素是 $S,T$ 中的一种，有 $C=AB$。
每个对象是 $S$ 中若干对象组成的一坨一坨的序列，有 $C=\frac 1 {1-A}$。
每个对象是 $S$ 中若干对象组成的多重集，无标号。
这个操作称为“欧拉变换”，记作 $\mathcal E(A(x))$。这个东西是一个完全背包，考虑 dp 的过程，每个物品相当于给答案的 OGF 乘上 $(1+x^i+x^{2i}+\dots )$ 于是我们有
- 每个对象是 $S$ 中若干对象组成额不可重集，无标号。
其实就是 01 背包，就是 $\prod (1+x^i)^{a_i}$
- 每个对象是 $S$ 中某个对象中的所有元素替换为 $T$ 中的一个对象：
通常用于递归结构，也就是 $A(B(x))$
CF438E The Child and Binary Tree
考虑命名并求解。
$f[n]$ 表示权值为 $n$ 的二叉树的个数
那么我们有
$f[n]=[n=0]+\sum{i=1}^{m}\sum{j=0}^{n-c_i}f[j]f[n-c[i]-j]$
这个东西不是很好做，但是假如我们定义 $F(x)$ 为 $f$ 的生成函数， $C(x)$ 为每个值在 $c$ 中出现次数的生成函数，那么有：
通过发现 $-$ 是不收敛的，我们可以得到
需要求逆，开根，再卷积三个操作。
考虑分子有理化，这样我们只剩下分母，就可以直接求了。
又或者，你比较强大，直接对着最开始那个柿子做牛顿迭代也可以。
我人手推了一下，大概是 $F=F_0/2-1/(2CF_0)$
我们也可以注意到牛顿迭代要求 $H$ 函数求导不能是常数，不然就寄了。
CF917D Stranger Trees
首先这种题还是先想有没有 dp 做法。
$f[n]$ 表示恰好有 $n$ 条边与已知边重复，这个不是很好做，考虑转化成至少 $n$ 条边与已知边重复，再根据二项式定理转回去。
直接做的话，脑补一下，我们需要枚举连通块的数量和大小，把连通块之间连起来，这里有个柿子是 $\prod a_i n^{k-2}$ 其中 $k$ 是连通块数量， $a_i$ 是每个连通块大小，我们直接 dp 做这个事情。
$f[i][j][k]$ 表示考虑了以 $i$ 为根的子树划分出 $j$ 个连通块，并且当前点所在连通块大小为 $k$，这样可以直接转移做到 $O(n^3)$。
考虑再次加强这个问题，我们直接考虑原来问题的 $\prod a_i$ 实际含义是每个连通块恰好选一个关键点，方案数，因此我们可以把第三维压缩到 $O(1)$，就可以做到 $O(n^2)$。
好接下来看完了如此优秀的 dp，我们想一下 OGF 的做法。
考虑生成树计数。一个套路是给每个树边一个权值 $1+x$，那么你做完矩阵树得到的多项式的第 $[x^i]$ 就是答案。这个操作也类似地应用在联合省选2020D2T3。
没完呢，考虑暴力直接硬算复杂度是 $O(n^4\log n)$ 的，会直接寄掉。
不过我们有一个小妙招。
我们只考虑前 $n$ 项，也就是我们对高于 $n$ 的次项是不关心的，因此我们直接把 $1\sim {n+1}$ 代入 $x$ 做高斯消元，得到的东西做拉格朗日插值即可。
这个东西本质上是把 DFT 操作放到了所有操作的最前面，类似地，你也可以对 $1+x$ 这个多项式做 DFT 然后点乘起来再做 IDFT 一样也可以得到结果。
能不能用生成函数直接大力这个题？我觉得是可以的，但是我不会。
P4389 付公主的背包
这题真是太经典了。
我们首先考虑暴力，就是经典的完全背包，如果我们把第一维展开（生成函数里的一个常见技巧），会得到 $f[n]=\sum_{i_1+i_2+i_3+\dots +i_k=n}g_1[i_1]g_2[i_2]\dots g_k[i_k]$，其中 $g_k[i_k]$ 表示第 $k$ 个物品凑出来 $i_k$ 的方案数。
那么显然，这个东西的生成函数等价于 $F=\prod G_i$，因此我们只需要算这个东西就行了，其中
因此实际上我们要求
考虑优化这个东西，这个优化也喜闻乐见。
首先这个东西一看就很可以取对数。
我们需要把里面那个东西干出来，这个玩意好像也是典的，直接代入 $\ln$ 泰勒展开可以得到：
于是我们直接把这些多项式加起来求 exp 就行了。
十二重计数法 X
求 $n$ 划分为 $m$ 个无序自然数之和的方案数。
首先把这 $m$ 个自然数排序，然后顺时针旋转 90°，问题变成求值域在 $[1,m]$ 的若干数组合为 $n$，显然就是 $\prod\frac 1 {1-x^i}$。
EGF
EGF 叫做指数生成函数。
啥意思？你看看形式就知道了。
那么 $<1,1,1,1,1,\dots>$ 的 EGF 就是 $e^x$，指数生成函数因此得名。
指数生成函数的用处是卷积。
这个柿子，你把它展开，把 $n!$ 除到左边，恰好就是指数生成函数的形式。
这个卷积的含义是，我有 $n$ 个有序点，标号 $1,\dots n$，这些点我挑出其中 $i$ 个放 $f[i]$，其他的放 $g[i]$ 的方案数。类似于一个归并。
常见的 EGF 就刚才那一个。
不常见的还有一个：
是
原因是显然的。
注意到一个东西，就是 EGF 卷积无法等价于背包，因为它有顺序。
考虑带标号组合类的无标号组合（感觉很绕，就是你看某些标号选还是不选）
给个例题。
例题
给出一个集合 $S$，求环大小在 $S$ 内的 $1\dots n$ 元置换的个数。
考虑大小为 $n$ 的环有 $(n-1)!$ 个，那么单个环的 egf 就是
考虑这个东西的含义是，我钦定它是个环，那么这 $n$ 个点的有标号计数是 $(n-1)!$，接下来我们要求这些东西拼起来得到的东西，也就是置换。
直接求 $\exp$ 就做完了。
换句话说，这里的 $\exp$ 其实是把单位元素的构成方案拓展到所有元素的构成方案，类似于单位事件和事件的关系。
比如连通图和图也满足这样的关系。
P4841 [集训队作业2013]城市规划
刚说完，这个题正好反过来了。
我们考虑求出 $f[n]$ 表示 $n$ 个点的有标号无向图的个数。
这个显然是 $2^{\binom n 2}$。
于是我们就可以把 $f$ 代表的 EGF 取自然对数，得到的就是连通图。
非常巧妙。
这里类似于一个反演的关系，我们不妨叫他 exp 反演。
P5748
求出 $Bell(n)$ 表示将集合 ${1,2,3,\dots n}$ 划分为若干无标号非空子集的方案数。
第二类斯特林数的行和就是贝尔数。
首先因为有标号，我们进行一个 EGF。
考虑一个子集的 EGF 是 $exp(x)-1$，所以你把若干个集合选出来就是 $exp(exp(x)-1)$。
P5162 WD与积木
先考虑只统计方案数。
单个集合方案是 $<0,1,1,1,1>=e^x-1$。
我们直接 $\sum (e^x-1)^i=\frac 1 {2-e^x}$ 就是整体的 EGF。
然后我们直接拿 $e^x-1$ 就可以得到答案的生成函数。
这个算是用求导和位移算，也可以用无穷级数求和。
因此答案就是
别被 $e^x$ 吓到了，直接算就行了。
这个题很强大，关键是要想到第一步，也就是单个集合的 egf，当一个集合大小为 0 的时候是不计入方案的，知道这个就可以直接 egf 求答案了，因为原题集合是无序的但是数字是有序的所以要用次幂直接乘起来。
简单图计数
无向图计数
$2^{\binom{n}{2}}$
有向图计数
$2^{n(n-1)}$
竞赛图计数
$2^{\binom{n}{2}}$
无向连通图计数
令无向图的 EGF 为 $F(x)$，无向连通图的 EGF 为 $G(x)$，有 $G=\ln F$
强连通竞赛图计数
竞赛图可以看作强连通竞赛图的序列，点有标号。
竞赛图的 EGF 为 $F$，强连通竞赛图的 EGF 为 $G$，有 $F=\frac 1 {1-G}$，那么 $G=\frac {F-1} F$。
注意 $F[0] = 1$，因为你要求逆。