这个东西不和那些紫题算法放在一起，因为生成函数好多都是黑题。
这篇文章的风格大概是 『题目+ 口胡 解法+启发』 ，在阅读这些乱七八糟的东西之前，可能需要一点点的 $door$ 项式基础（大概学到 $\exp$ 就够了？）。
伟大的 $\mathbf{Pólya}$ 生前曾经说过：
『生成函数就像装东西的袋子，我们如果拿着一个个东西会很尴尬，（有了生成函数）我们就只需要拿一个东西——袋子』
生成函数如同晾衣架，他把一个个数晾在系数上，我们需要的不是晾衣架本身，而是晾着的衣服们。
那么我们可以随便开一道题来爽一爽。
[集训队作业2013]城市规划
x义x 神仙名著《生成函数再入门》的第一题。
题目大E是有标号无向连通图计数。
我们开两个数组 $f[n]$ 表示 $n$ 个点的有标号无向 联通 图的个数， $g[n]$ 表示 $n$ 个点的有标号无向 不管联不联通 图。
很显然， $f[n]$ 就是我们想要的答案。
而 $g[n]$ 是很好求的，考虑任意两点间的边 连或不连 即可，有 $g[n]=2^{\binom{n}{2}}$ 。
$f$ 和 $g$ 之间有什么微妙关系呢？
接下来的操作有两条路可走，但它们是殊途同归的，建议两个都看一看。
暴推式子出口方向：
一个 $n$ 个点的 不管联不联通 图一定是 【$1$ 号点所在的大小为 $k$ 个点的 联通 图】和【剩余 $n-k$ 个点的 不管联不联通 图】合起来得到的。
我们称 $1$ 号点所在的大小为 $k$ 个点的 联通 图为 【 $1$ 号联通图 】。
而那些在【 $1$ 号联通图】里的（除 $1$ 号点外）其它 $k-1$ 个点则也需在所有 $n-1$ 个点中进行一番选择，需要多乘一个 $\tbinom{n-1}{k-1}$。
也就是：
组合数暴拆之：
活得像个 $\text{EGF}$ 。设：
结合上式，有 $H=F G$ ，即 $F=H G^{-1}$ ，那么只要会求逆即可。
$\exp$ 组合意义出口方向：
很显然，一个 不管联不联通 图是由若干个 联通图 组成的，也就是把 $n$ 个点划分到几个集合中，每个集合是一个 联通图 。
那么就是【集合划分计数】了，这是 $\exp$ 的组合意义。
即可科技。
设 $F$ 是 $f[i]$ 的 $\text{EGF}$ ，$G$ 是 $g[i]$ 的 $\text{EGF}$ ，也就有！
那么只要会多项式劳茵即可。
先辈在召唤：
数东西普遍可以开两个数组，一个数组和答案 直接相关 ，一个数组 极为易求 ，两数组之间又有可行的 转移 即可。
拆组合数 可以把卷积中看上去很烦的系数溶进 $\text{EGF}$ 里
$\text{exp}$ 的组合意义是把 有标号 小球划分到几个箱子里，不能空箱
The Child and Binary Tree
x义x 神仙名著《生成函数再入门》的第二题。
这道题的通过人数就比上一题明显少了，或许是上一题露出了数数深渊的冰山一角。
大E是给定可选权值的集合，求构造一棵 点有点权 ， 权值和为 $S$ 的二叉树的方案数。
首先，思尻一下，若可选的权值不限，求 $K$ 个元素总权值为 $S$ 的方案数，怎么搞？
这是母函数板子。参考配硬币。
我们设 $f[i]$ 表示权值和为 $i$ 的方案数，有：
加了可选的权值限制呢？
多加了一个 $g[i]$ ，表示权值 $i$ 是否（1/0）可选。
那么有：
即先查 $S-i$ 这个权值是否合法，再配硬币配出 $S-i$ 。
那么把这个问题上树呢？
事实是式子也是一样的，考虑配金币的过程。$f[j]* f[S-i-j]$ 其实就是在尝试“一棵子树权值和为 $j$ ，另一棵子树权值和为 $S-i-j$ ”的造树方法。
那么随手改写成卷积：
_（因为$G[0]=0$ ，导致常数项 $(G*F)[0]=1$ 在 $G$ 和 $F$ 的卷积中丢掉了，所以补一个 $1$）_
在这里有的题解是直接一元二次求根公式的，但您应该注意，$G[0]=0$ ，也就是说 $G$ 是不可求逆的。以下应该才是正确的推倒方式。
先小力配方：
再小力分讨：
- 当 $GF+\dfrac{1}{2}=\sqrt{\dfrac{1}{4}-G}$
注意到这个右式的零次项是 $\dfrac{\sqrt{1-0}+1}{2}=1$ ，然而 $GF$ 一卷零次项应该是 $0$ ，所以舍正。
- 当 $GF+\dfrac{1}{2}=-\sqrt{\dfrac{1}{4}-G}$
这个右式的零次项是 $\dfrac{-\sqrt{1-0}+1}{2}=0$ ，符合条件，故取负。
最后小力化式子：
只要会零次项为 $1$ 的多项式开方和多项式求逆即可。
先辈在召唤：
当我们有某个权值是否可选的限制时，可以开一个装 $0/1$ ，表示权值 是否可用 的 $G$ 数组去和正经的 $F$ 卷一卷。
一个多项式 $F$ 可以求逆的前提是 $F[0]\neq0$ ，可以开方的前提是 $F[0]\geq 0$ （有时 $F[0]=0$ 时不可开方，那是特例）。
注意观察零次项，零次项有时需要在推式子过程中 补全 ，常数项的存在有无有时可以帮助我们 舍掉一些情况 。
[国家集训队]整数的lqp拆分
x义x 神仙名著《生成函数再入门》的第三题。
事实上笔者学数数的最初一段时间就是对着x义x神仙的文章摸♂索与练♂习的，这里表示感谢与膜拜。
大E是正整数拆分，拆分出的数装在 $a$ 里，定义一个方案的贡献是 $\prod fib[a[i]]$ ，求总贡献。
设 $f[i]$ 表示和为 $i$ 的拆分的总贡献，显然我们的答案是 $f[n]$ 。
有一个极其一眼的递推式：
即，假设目前是第一次拆分，枚举这次将被拆分出的数，把 剩余部分 的总贡献乘以 拆分出这个数时 所得的贡献
其实就是把配硬币的新方案贡献换成了 $fib[k-i]$ 。
随手写成卷积，设 $F$ 是 $f$ 的 $\text{OGF}$ ，$G$ 是 $fib$ 的 $\text{OGF}$ 。
有：
（依然需要 $0$ 次项补全）
如果您有初中水平，那么您应该知道 $G(x)=\dfrac{1}{1-x-x^2}$ ，下面是推倒：
把一个多项式乘 $x$ 相当于是把其系数 向右平移 的过程。
我们发现如果把 同次项对齐，我们惊奇地发现在非零次项上，都有 $G[i]-(xG)[i]-(x^2G)[i]=0$ ；而在零次项上 $G[0]-(xG)[0]-(x^2G)[0]=1$ 。
也就是说 $G-xG-x^2G=1$ ，那么 $G(x)=\dfrac{1}{1-x-x^2}$ ！
$\Box$
回到我们卷出来的式子：
也就有了：
一通操作化得：
我们说过，生成函数是晾衣架，我们要的是 $x$ 的系数，从这个分式里显然看不出，我们得把它化成 $\text{OGF}$。
想到 $\dfrac{1}{1-cx}=\sum_{i=0}^{\infty} c^ix^i$ ，我们尝试把右边那个鬼化成 $\dfrac{x}{(1-ax)(1-bx)}$ 这种形式。
实数域上因式分解分母有，注意到两因式差为 $2\sqrt{2}$ ，裂项即可：
非常惭愧，只做了一些微小的工作。
这样我们就有 $\text{OGF}$ 的曙光了。
时刻牢记 $F(x)$ 代表的是关于 $x$ 的多项式，而 $F[x]$ 代表的是多项式第 $x$ 项的系数。
因为常数项 $1$ 是为了使 $f[0]=1$ ，之后就不再管了。
枚举可得 $\sqrt{2}$ 在膜 998 意义下为 $59713600$ ，爆算即可，不需要多项式科技。
先辈在召唤：
斐波那契数列的生成函数是 $\dfrac{1}{1-x-x^2}$ ，可以采取 平移+对齐同次项观察系数 的方式得出（这种方法可以沿用到其它数列的推导）
时刻分清 晾衣架（生成函数本体）和晾着的衣服（系数） 之间的差异，必要时在草稿上用不同变量名。
面对要用 “大”分式生成函数 想求它的系数时，可以拆成若干个 $\dfrac{1}{1-cx}$ 相加减，然后改写为 $c^i$ 即得系数的通项公式。
差分与前缀和
大E是求一个数列的 $k$ 阶差分或前缀和。
水平不够，没什么时间写了
最后更新： 2021年04月17日 16:14