关于生成函数
关于生成函数
基础
普通生成函数
对于数列 \(a_i\) ，它的普通生成函数( \(\text{OGF}\) )为 \(A(x)=\sum a_ix^i\)。
这个 \(x^i\) 刚开始并没有实际意义，即为形式幂级数，实际这个 \(i\) 甚至可以不是一个整数，如 \(\text{FWT}\) 中的指数为集合幂指数。
普通生成函数常用于解决无序的组合计数问题，如背包问题。
常见背包的生成函数
我们让 \(x^i\) 项表示选择了 \(i\) 个物品，则可以构造生成函数。
一个01背包，每一个物品的生成函数为 \(A(x)=x+1\) ，其中 \(x\) 项表示多选了一个，1 项表示空着不选。
同理，对于一个有限背包，每个物品上限 \(m_i\) ，则 \(A_i(x)=\sum_{j=0}^{m_i} x^j\)。
一个完全背包的生成函数为 \(\begin{aligned} A(x)=\sum_{i=0}^{\infty} x^i=\frac{1-x^{\infty}}{1-x}=\frac{1}{1-x}\end{aligned}\) （因为我们所求的答案是前若干项，无穷项没有意义）。
那么多个物品的组合就可以通过这些生成函数相乘来轻松表示，因此也容易被多项式的快速运算优化。
用生成函数描述递推关系
一个最简单的例子，设斐波那契数列的普通生成函数为 \(F(x)\)。
我们知道 \(F_i=F_{i-1}+F_{i-2},F_0=0,F_1=1\)。
则可以用生成函数表示斐波那契数列的递推关系 \(F(x)=x F(x)+x^2 F(x)+x\)。
其中 \(xF(x)\) 对应递推式的 \(F_{i-1}\) ， \(x^2F(x)\) 对应递推式的 \(F_{i-2}\) ， \(x\) 对应 \(F_1\) 的值。
类似的问题还包括数列的线性递推，即 \(a_i=\sum b_ja_{i-j}\) ，但是这个求解比较复杂。。。
基于概率期望的生成函数
取自 集训队论文 2018 - 1 浅谈生成函数在掷骰子问题上的应用长沙市长郡中学杨懋龙。
对于随机非负离散变量 \(x\) ，令它的概率生成函数是 \(F(z)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)z^i\end{aligned}\) ，则可以看到这里的指数代表 \(x\) 的值。
\(x\) 的值不一定能够相加，但是利用这个生成函数，可以快速表达期望，方差等，具体见下式：
\(F(1)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)=1\end{aligned}\)
\(F'(1)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot i=E(x)\end{aligned}\)
\(E(x^{\underline{k}})=F^{(k)}(1)\) ( \(x\) 的 \(k\) 阶下降幂，( \(k\) )表示 \(k\) 阶导数)
\(x\) 的方差 \(=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot (i-E(x))^2\end{aligned}=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot i^2-2P(x=i)\cdot i\cdot E(x)+P(x=i)\cdot E^2(x)\end{aligned}\)
\(=E(x^2)-2E^2(x)+E^2(x)=E(x^2)-E^2(x)=E(x^{\underline{2}})+E(x)-E^2(x)=F''(1)+F'(1)-(F'(1))^2\)
可以作为导数在生成函数推导中应用的一个例子。
指数生成函数
对于数列 \(a_i\) ，它的指数生成函数（ \(\text{EGF}\)）为 \(\begin{aligned} A(x)=\sum \frac{a_ix^i}{i!}\end{aligned}\)。
指数型生成函数是处理有序排列问题的一大利器，因此，指数上的 \(i\) 通常表示个数。
为什么 \(\frac{1}{i!}\) 可以简化排列问题，可以参见这样的一个例子。
用若干类物品排成一个排列，每一类有 \(m_i\) 个，则不同的排列个数为 \(\begin{aligned} \frac{(\sum m_i)!}{\prod m_i!}\end{aligned}\)。
这个式子的意义就是: 假设先随便排列，由于每一类相同，因此类之内的排列都要除掉。
可以看到， \(\frac{1}{i!}\) 描述的就是类内的排列，因此最后求得答案项还要乘上 \(n!\)。
如果一类物品任意个数加入排列，则其指数生成函数为 \(\begin{aligned} A(x)=\sum_{i=0}^{\infty}\frac{x^i}{i!}=e^x\end{aligned}\)。
根据 \(e^{-x}=\sum_i \frac{(-x)^i}{i!}\) ,还能得到：
限制为偶数个的指数生成函数 \(\begin{aligned} A(x)=\sum_{2|i}^{\infty}\frac{x^i}{i!}=\frac{e^x+e^{-x}}{2}\end{aligned}\)，
限制为奇数个的指数生成函数 \(\begin{aligned} A(x)=\sum_{2|i}^{\infty}\frac{x^i}{i!}=\frac{e^x-e^{-x}}{2}\end{aligned}\)。
限制为 \(n\) 的倍数个，较为复杂，需要用到单位根反演。
\(e^{x}\) 在排列问题叠加上的应用
若有一类等价排列子问题，其指数型生成函数为 \(F(x)\) ，则任意叠加其得到的排列问题指数型生成函数为。
\(\begin{aligned} \sum_{i=0}^{\infty} \frac{F^i(x)}{i!}=e^{F(x)}\end{aligned}\) ，其中 \(\frac{1}{i!}\) 表示除去子问题之间等价。
更多常用技巧
分治NTT解决多个多项式卷积问题
CDQ分治NTT解决有序递推问题
推导生成函数的关系
树的递归关系：
问题：计算合法树的数量，如树上染色问题等。
这一类问题可以表示为 一种递归关系，即 枚举根的状态 加上根的儿子对应的生成函数，
例子 [Codeforces Round #250]小朋友和二叉树 。
设一个点的生成函数为 \(G\) ，整棵数的生成函数为 \(F\) ，其中幂指数代表权值和，则 \(G\) 是我们已知的，且有关系
\(F=G\cdot F^2+1\) ，其中 \(F^2\) 表示枚举两个子树的状态， \(G\) 表示枚举根的状态， \(+1\) 表示空树。
类似这样的问题还有 烷基计数加强版加强版 这个方程要用到牛顿迭代求解
集合幂指数在处理 01 状态上的应用
如果用整数指数形式表示的生成函数解决 01 状态上的 or,and, xor操作。
我们通常需要把这个过程转化为对 \(0,1\) 个数来做。
但是这一类的问题，通常可以用集合幂指数轻松表示，前提是你了解 \(\text{FWT}\) 卷积三种类型的本质过程。