生成函数

发表于 分类于

生成函数知识点总结。

简单的介绍

对于一个序列 ${a_0,a_1\cdots}$，我们想把这个数列表示出来，把它写成一个函数的形式。因此就有了以下的两种形式：

  • 普通型生成函数(OGF)：$f(x)=\sum_{i=0}a_ix^i$ ，主要用来解决无标号，组合问题。

  • 指数级生成函数(EGF)：$f(x)=\sum_{i=0}\frac{a_i}{i!}x^i$ ，主要用来解决有标号，排列问题。

主要和多项式各种运算搭配使用。

一些例子：

OGF：

  • ${ 1,1,1,\cdots}$ 的OGF为：$\sum_{i=0}x^i=\frac{1}{1-x}$

  • ${ 1,a,a^2,\cdots}$ 的OGF为：$\sum_{i=0}a^ix^i=\frac{1}{1-ax}$

  • ${ 1,-1,1,-1,\cdots}$ 的OGF为：$\sum_{i=0}(-1)^ix^i=\frac{1}{1+x}$

  • $\frac{1}{1-x}$ 求 $n$ 次导得到的是杨辉三角第 $n+1$ 列的数。

EGF：

  • ${1,1,1,\cdots}$的EGF为：$\sum_{i=0}\frac{x^i}{i!}=e^x$
  • $\frac{e^x+e^{-x}}{2}=\sum_{i=0}\frac{x^{2i}}{(2i)!}$
  • $\frac{e^x-e^{-x}}{2}=\sum_{i=0}\frac{x^{2i+1}}{(2i+1)!}$
  • $\ln(1-x)=-\sum_{i=1}\frac{x^i}{i}$

应用

图计数问题

以下问题，$n\leq 10^5$。模$998244353$。

带标号无向图数量

$f_i=2^{\binom{i}{2}}$

带标号无向连通图数量

设答案为$g_i$，其生成函数为$G$，第1题的生成函数是$F$，那么一个无向图就是由一些无向连通图组合起来的。

那么可以枚举一个无向图是由多少个连通图组成的，假设为$i$，那么答案跟$F^i(x)$所对应的系数有关系。因为无序，所以要除一个$i!$，因此有：

$F(x)=\sum_{i=0}^{\infty}\frac{G^i(x)}{i!}=e^{G(x)}$

同时求$\ln$得$G(x)=\ln F(x)$

多项式求$\ln$即可。

带标号DAG数量

很明显先dp，设$f_i$为$i$个点带标号的DAG数量。$f_0=1$。先假设有$j$个点度数为0，符合上述条件的$j$个点的集合有$\binom{i}{j}$个；这$j$个点可以任意向其他$i-j$个点连边，方案数有$2^{j(i-j)}$个；剩下的$i-j$个点也必须是个DAG，方案数为$f_{i-j}$乘法原理得方案数为$\binom{i}{j}2^{j(i-j)}f_{i-j}$，可是剩下的$i-j$个点中也还是有一些度数为0的点的，那么容斥一下就好了。

得到dp方程式：$f_i=\sum_{j=1}^i(-1)^{j-1}\binom{i}{j}2^{j(i-j)}f_{i-j}$

时间复杂度$O(n^2)$

考虑优化，式子右边很像一个卷积形式，但是$2^{j(i-j)}$很难化简。。。

可以发现，$2^{j(i-j)}={2^{j^2}}\times {2^{-ij}}$，有没有办法把$-ij$化成只跟$j$和$i-j$和$i$有关的东西乘起来呢？

初中知识：$(i-j)^2=i^2+j^2-2ij$

因此$2^{i(i-j)}={2^{i^2}}\times {2^{-ij}}=(\sqrt{2})^{i^2-(i-j)^2-j^2}$

那$\sqrt{2}$在模$998244353$意义下是什么来的呀？

不用怕，$2$在模$998244353$意义下有二次剩余的呢。

因此$dp$式可化成：

$$\frac{f_i}{(\sqrt{2})^{i^2}i!}=\sum_{j=1}^i\frac{(-1)^{j-1}}{(\sqrt{2})^{j^2}j!}\times \frac{f_{i-j}}{(\sqrt{2})^{({i-j})^2}(i-j)!}$$

设$F(i)=\frac{f_i}{(\sqrt{2})^{i^2}i!}$,$G(i)=\frac{(-1)^{i-1}}{(\sqrt{2})^{i^2}i!}(i\geq1)，G(0)=0$

那么$F=GF+1$，即$F=\frac{1}{1-G}$

多项式求逆，时间复杂度$O(n \log n)$

带标号的DAG数量，要求图弱连通

和第二题是一样的。设$H(x)$为该题答案的指数型生成函数，$F(x)$为第三题的指数型生成函数，那么$F(x)=e^{H(x)}$，$H(x)=\ln F(x)$，多项式求$\ln$即可。

拉格朗日反演

若两个函数 $F(x),G(x)$ 满足：$F(G(x))=x$。

则有：$[x^n]G(x)=\frac{1}{n}[x^{n-1}] (\frac{x}{F(x)})^n$

证明：懒得证了，会用就行。