生成函数
1 OGF
OGF，也就是普通型生成函数，可以帮助我们解决一些数列问题，组合问题。
对于一个数列 \(\)，我们可以假设它的普通型生成函数为 \(A(x)=\sum\limits_{i\ge0}a_ix^i\)。
那么，我们发现，这个函数 \(A(x)\) 的加减对应着数列的加减。
如果乘上一个 \(x\)，那么 \(x\cdot A(x)=\sum_{i\ge 0}a_ix^{i+1}\)，也就是说，对应到数列上，相当于右移了一位，变成 \(<0,a_0,a_1,\dots>\)。
同理，除掉一个 \(x\) 也对应左移操作。
根据这个性质，我们可以处理一些简单问题：
问题 1.1：利用生成函数求出斐波那契数列的通项公式。众所周知，斐波那契数列的递推公式为：\(F_i=\begin{cases}1&(i\le1)\\F_{i-1}+F_{i-2}&(i\ge 2)\end{cases}\)
那么，假设斐波那契数列的 OGF 为 \(F(x)\)，则：
【生成函数】
\[F(x)=\sum_{i\ge0}F_ix^i \]
\[=1+x+\sum_{i\ge2}(F_{i-1}+F_{i-2})x^i \]
\[=1+x+x\sum_{i\ge1}F_ix^i+x^2\sum_{i\ge0}F_ix_i \]
\[=x^2F(x)+xF(x)+1 \]
然后，把 \(F(x)\) 当成未知数，\(x\) 当参数，就可以解方程了，就能得出 \(F(x)\) 的有限项代数式。
\[F(x)=\frac 1{1-x-x^2} \]
然后就是老套路了，我们把 \(\dfrac1{1-x-x^2}\) 写成 \(\dfrac{R}{1-rx}+\dfrac{S}{1-sx}\) 的形式，就可以利用等比数列求和公式展开了。
假设我们已经求出来了，那么，我们就能够得到：
\[F(x)=\frac R{1-rx}+\frac S{1-sx} \]
\[=R(r^0x^0+r^1x^1+r^2x^2+\dots)+S(s^0x^0+s^1x^1+s^2x^2+\dots) \]
\[=\sum_{i\ge0}(Rr^i+Ss^i)x^i \]
\[\therefore F_i=Rr^i+Ss^i \]
接下来唯一的问题就是求出 \(R,S,r,s\) 了。
我们通分：\(\dfrac{R(1-sx)+S(1-rx)}{(1-rx)(1-sx)}=\dfrac{1}{1-x-x^2}\)，分子分母每一项都对应，所以得到：
\[\begin{cases} S+R=1\\ Rs+Sr=0\\ r+s=1\\ rs=-1 \end{cases} \]
解出来就行。
问题 2.2：利用生成函数求出卡特兰数的通项公式。虽然之前我们已经用经典翻折容斥求出了卡特兰数的通项公式，但是，我们同样可以用生成函数求出。
我们已经知道卡特兰数的递推公式：\(C_0=1,C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i}\)，发现这个就是一个卷积形式，但有不完全是，卷积完之后向右移了一位。
所以，假设卡特兰数的 OGF \(C(x)=\sum\limits_{i\ge0}C_ix^i\)，那么：
\[C(x)=xC^2(x)+1 \]
\[C(x)=\frac {1\pm\sqrt{1-4x}}{2x} \]
发现这里有正负号，到底取那个呢？
我们考虑把 \(x=0\) 的情况带进去，那么 \(C(0)=C_0=1\)。
我们发现，\(\lim\limits_{x\rightarrow 0}\dfrac{1\pm\sqrt{1-4x}}{2x}=\lim\limits_{x\rightarrow 0}\dfrac{2}{1\mp\sqrt{1-4x}}\)，所以舍去正号解，所以 \(C(x)=\dfrac{1-\sqrt{1-4x}}{2x}\)。
那么我们应该如何展开呢？
我们之前提过广义二项式定理，在这里就派上用场了。
\[C(x)=\frac 1{2x}(1-\sum_{i\ge0}\dbinom {\frac 12}i(-4x)^i) \]
\[=\frac 1{2x}(1-(1+\sum_{i\ge1}\frac{\frac 12\cdot(-\frac 12)\cdot\dots\cdot(-\frac {2i-3}{2})}{i!}(-4x)^i)) \]
\[=2\sum_{i\ge1}\frac{\frac 12\cdot(-\frac 12)\cdot\dots\cdot(-\frac {2i-3}{2})}{i!}(-4x)^{i-1} \]
\[=2\sum_{i\ge1}\frac{\frac 12\cdot\frac 12\cdot\dots\cdot\frac {2i-3}{2}}{i!}(4x)^{i-1} \]
\[=1+\sum_{i\ge2}\frac{1\cdot 3\cdot\dots\cdot(2i-3)}{i!}(2x)^{i-1} \]
\[=1+\sum_{i\ge2}\frac{(2i-3)!!}{i!}(2x)^{i-1} \]
\[=1+\sum_{i\ge2}\frac{(2i-3)!!(2i-2)!!}{i!(i-1)!}x^{i-1} \]
\[=1+\sum_{i\ge2}\frac{(2i-2)!}{i!(i-1)!}x^{i-1} \]
\[=1+\sum_{i\ge1}\frac{(2i)!i}{i!i!}x^i \]
\[=\sum_{i\ge0}i\dbinom {2i}ix^i \]
\[\]
至此，我们的工作就结束了，我们得出 \(C_n=n\dbinom {2n}n\)，和我们之前的结论一致。
问题 1.3（P2000 拯救世界）：题目太长，懒得写题目其实非常简单，可以直接每一项上 OGF，用等比数列求出，全部乘起来即为答案，最后结果发现都可以约掉，剩下 \(\dbinom n4\)，然后就是高精度了。
练习：
P6694 强迫症
CF438E The Child and Binary Tree
P4451 [国家集训队]整数的lqp拆分
2 EGF EGF 是指指数型生成函数，与 OGF 不太相同的生成函数。废话
我们假设一个无限数列 \(\)，我们假设它的指数型生成函数 \(A(x)=\sum\limits_{i\ge0}a_i\dfrac{x^i}{i!}\)。
为什么要这么设呢？暂时保留这个问题，看到后面就会知道了。
问题 2.1：探究指数型生成函数进行一些函数的基本操作的性质。我们探究一下这个指数型生成函数的性质：
加减法就不多说了，如果我们给 \(A(x)\) 乘上一个 \(x\) 会发生什么事呢？
\[x\cdot A(x)=\sum_{i\ge 0}a_i\frac{x^{i+1}}{i!} \]
\[=\sum_{i\ge 0}a_i(i+1)\frac{x^{i+1}}{(i+1)!} \]
\[令\ a_{-1}=0，则： \]
\[x\cdot A(x)=\sum_{i\ge0}a_{i-1}i\frac{x^i}{i!} \]
也就是说，乘法操作会使数列从 \(\) 对应成 \(<0,1a_0,2a_1,\dots>\)，区别于 OGF 中的位移操作。
目前来说，还不清楚这个操作有什么用。最起码笔者并不会。
如果对 \(A(x)\) 进行求导呢？
\[A'(x)=\sum_{i\ge0}ia_i\frac{x^{i-1}}{i!} \]
\[=\sum_{i\ge0}a_i\frac{x^{i-1}}{(i-1)!} \]
\[=\sum_{i\le 0}a_{i+1}\frac{x^i}{i!} \]
我们发现，对函数 \(A(x)\) 求导之后，数列 \(\) 对应到了 \(\)，对应了数列上的左移操作。
同理，用同样的方法，我们也可以推出：指数型生成函数的积分对应数列的右移操作。具体证明这里就不放了。
如果是卷积操作呢？
\[F(x)=G(x)H(x) \]
\[=\sum_{i\ge0}\sum_{j+k=i}\frac {g_j}{j!}\cdot\frac{h_k}{k!}\frac{i!x^i}{i!} \]
上面的 \(i!\) 是为了保持指数型生成函数的队形。也就是说，我们能够得到这样的式子：
\[f_n=n!\sum_{i+j=n}\frac{g_ih_j}{i!j!} \]
我们发现 \(\dfrac{n!}{i!j!}\) 可以写成组合数的形式：
\[f_n=\sum_{i=0}^n\dbinom nig_ih_{n-i} \]
也就是说，指数型生成函数的卷积对应的是类似于组合问题，可以考虑组合含义，解决一些计数问题。
至此，我们开头提出来的问题已经解决：
EGF 可以用来求解任意组合问题。EGF 相关形式会有一些封闭式，和泰勒展开有关。因为笔者太菜，不太会证明，所以就直接放结论了。
\[e^x=\sum_{i\ge0}\frac{x^i}{i!}=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots \]
\[e^{-x}=\sum_{i\ge0}\frac{(-x)^i}{i!}=1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\dots \]
\[\frac{e^x+e^{-x}}2=\sum_{i\ge0}\frac{x^{2i}}{(2i)!}=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}+\dots \]
\[\frac{e^x-e^{-x}}2=\sum_{i\ge0}\frac{x^{2i+1}}{(2i+1)!}=x+\frac{x^3}{3!}+\frac{x^5}{5!}+\frac{x^7}{7!}+\dots \]
\[\ln(1+x)=\sum_{i\ge1}\frac{(-x)^i}{i}=x-\frac{x^2}2+\frac{x^3}3-\frac{x^4}4+\dots \]
\[\sin x=\sum_{i\ge0}\frac{(-1)^ix^{2i+1}}{(2i+1)!}=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\dots \]
\[\cos x=\sum_{i\ge0}\frac{(-1)^ix^{2i}}{(2i)!}=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\dots \]
\[\]
还有就是在前面提过的广义二项式定理，也会经常出现：
\[(1+x)^a=\sum_{i\ge0}\dbinom aix^i \]
也可以写成这个形式：
我们定义下降次幂（FFP）为：
\[x^{\underline n}=x(x-1)(x-2)\dots(x-n+1) \]
\[(1+x)^a=\sum_{i\ge0}\frac{a^{\underline i}x^i}{i!}=1+ax+\frac{a(a-1)x^2}{2!}+\frac{a(a-1)(a-2)x^3}{3!}+\dots \]
对于有序，有标号之类的题目，就可以考虑使用 EGF 了。
下面我们来看几道 EGF 的例题。
例题 2.2（P2012 拯救世界2)：一个长度为 \(n\) 的串，有 \(12\) 中不同的元素，其中有 \(4\) 中只能出现奇数次，另外还有 \(4\) 种只能出现偶数次，求该串的方案数。我们发现，这一道题对比 P2000 的区别就是字符串有序，所以我们采用 EGF。
三种串，我们假设 \(f_n\) 表示正常元素构成一个长度为 \(n\) 的串的方案数，\(g_n\) 表示只能出现奇数次的，\(h_n\) 表示只能出现偶数次的。那么显然有：
\[f_n=1\\ g_n=\begin{cases}1&n\%2=1\\0&n\%2=0\end{cases}\\ h_n=\begin{cases}1&n\%2=0\\0&n\%2=1\end{cases} \]
设 \(A_n\) 为长度为 \(n\) 的串的答案，
然后答案显然就可以枚举每一种选了多少个：
\[A_n=\sum_{i_1+i_2+i_3+i_4+j_1+j_2+j_3+j_4+k_1+k_2+k_3+k_4=n}\dbinom{n}{i_1,i_2,i_3,i_4,j_1,j_2,j_3,j_4,k_1,k_2,k_3,k_4}f_{i_1}f_{i_2}f_{i_3}f_{i_4}g_{j_1}g_{j_2}g_{j_3}g_{j_4}h_{k_1}h_{k_2}h_{k_3}h_{k_4} \]
显然就是上面 EGF 卷积的形式，所以我们直接设三个函数的 EGF 为 \(F(x),G(x),H(x)\)，
根据前面的式子，我们就可以发现：\(F(x)=e^x,G(x)=\dfrac{e^x+e^{-x}}2,H(x)=\dfrac{e^x-e^{-x}}2\)。
那么答案的 EGF \(A(x)=(F(x)G(x)H(x))^4\)，
然后就是这一题稍微有点卡常，需要优化一下，把这些东西全部手算一下，写个光速幂。
还有就是本题模数是
1e9，不是质数，要用扩展欧拉定理。例 2.3（CF891E Lust）：你有一个数列 \(a_1,a_2,\dots,a_n\)，答案初始为 \(0\)，你要对数列进行 \(k\) 次操作，每次随机选择一个数 \(x \in [1,n]\)，把 \(a_x\) 减一，并将答案增加除 \(a_x\) 外所有数的乘积，求出最终答案的期望。我们发现这个答案的统计好像很难处理，考虑转化，每一次增加的答案其实就是操作前后 \(\prod a_i\) 的乘积的差，所以我们要求的问题可以这样描述：
有一个数列 \(a_1,a_2,\dots,a_n\)，和 \(n\) 个初始为 \(0\) 的数 \(c_1,c_2,\dots,c_n\)，\(k\) 次操作，每次选一个 \(c_i\) 增加 \(1\)，求 \(\prod a_i-\prod(a_i-c_i)\) 的期望对 \(1e9+7\) 取模。期望问题有一个常见求法就是转化为每种方案的和除以方案总数。方案总数显然是 \(n^k\)，所以我们只需要求出每种方案的和即可。
我们发现这个操作是有序的，比如先操作一次 \(c_1\)，再操作一次 \(c_2\) 和先操作一次 \(c_2\)，在操作再次 \(c_1\) 算作不同方案，虽然最后结果相同。
因此可以考虑 EGF。
整理一下前面的思路，设 \(Ans\) 表示答案，那么：
\[Ans=\prod_{i=1}^n a_i-\frac 1{n^k}\sum_{\sum c_i=k}\dbinom{k}{c_1,c_2,\dots,c_n}\prod_{i=1}^n (a_i-c_i) \]
上面的组合数就是每一种 \(c_i\) 的划分方式的方案数。
我们可以定义一个 \(a_i-c_i\)的 EGF：
\[f_i(x)=\sum_{j\ge0}\dfrac{(a_i-j)x^j}{j!} \]
拆开计算：
\[f_i(x)=a_i\sum_{j\ge0}\frac{x^j}{j!}-\sum_{j\ge0}\frac{x^j}{(j-1)!} \]
\[=a_ie^x-xe^x \]
\[=(a_i-x)e^x \]
显然，如果设 \(g_k=\sum_{\sum c_i=k}\dbinom{k}{c_1,c_2,\dots,c_n}\prod (a_i-c_i)\)，那么 \(g_k\) 的 EGF \(G(x)=\prod f_i(x)\)。
\[G(x)=\prod_{i=1}^n (a_i-x)e^x\\ =e^{nx}\prod_{i=1}^n (a_i-x) \]
也就是说，我们要求出上面这个多项式的 \(x^k\) 项系数。
假设我们已经求出了一个多项式 \(H(x)=\prod_{i=1}^n(a_i-x)=\sum_{i=0}^n h_ix^i\)，接下来我们把 \(e^{nx}\) 展开成 \(\sum_{i\ge0} \dfrac{n^ix^i}{i!}\)，那么：
\[[x^k]G(x)=\sum_{i=0}^k\frac{h_in^{k-i}}{(k-i)!} \]
于是，我们可以通过递推 \(O(k)\) 计算出这部分答案，最后记得乘以 \(k!\)。
至于 \(H(x)\) 怎么求，可以分治
NTT 做到 \(O(n\log^2n)\)，但是本题模数为 \(1e9+7\)，需要MTT，并且 \(n\le 5000\)，所以我选择直接 \(O(n^2)\) 暴力卷积！练习：
P5748 集合划分计数
P4841 [集训队作业2013]城市规划
P7364 有标号二分图计数
P6295 有标号 DAG 计数
P5401 [CTS2019] 珍珠
P5206 [WC2019] 数树
