生成函数
我理解为对某数列的一种描述/刻画。
在生成函数中在生成函数中，\(x\) 代表的意义并非未知数，也不具有任何值，而仅仅是一个代数对象。关注 \(x\) 的值或 \(F(x)\) 的值是没有意义的。
由于生成函数的理解和应用大多来自习题，我就把笔记与习题放在一起了。
OGF 普通生成函数
定义为形式幂级数：
\[\sum\limits_{i=0}a_ix^i \]也就是把某个序列用多项式进行刻画，通过 \(x\) 的不同幂次来区分每一项。
比如说，序列 \(a=\langle1,1,1,\dots\rangle\) 的生成函数为 \(F(x)=\sum\limits_{i=0}x^i\)
序列 \(a=\langle1,p,p^2,\dots\rangle\) 的生成函数为 \(F(x)=\sum\limits_{i=0}p^ix^i\)
换句话说，系数就是数列的通项公式。
基本运算
对于两个序列 \(a,b\) 的 OGF \(F(x),G(x)\)，有：
\[F(x)\pm G(x)=\sum\limits_{i=0}(a_i\pm b_i)x^i \]也就是 \(F(x)\pm G(x)\) 为序列 \(\langle a_n\pm b_n\rangle\) 的生成函数。
乘法运算，即卷积：
\[F(x)G(x)=\sum\limits_{i=0}x^i\sum\limits_{j=0}^{i}a_jb_{i-j} \]因此 \(F(x)G(x)\) 为序列 \(\langle\sum\limits_{i=0}^{n}a_ib_{n-i}\rangle\) 的生成函数。
以上内容 cpy 自 oiwiki。
封闭形式
幂级数不好写，而因为 \(x\) 仅仅为代数对象，它的值没有意义，我们也就不用考虑生成函数的敛散性了。
运用封闭形式可以方便生成函数的化简。
比如说，\(a=\langle1,1,\dots\rangle\) 的生成函数为 \(F(x)=\sum\limits_{i=0}x^i\)，我们有：
\[xF(x)=\sum\limits_{i=1}x^i \]作差，有：
\[(1-x)F(x)=1 \]即：
\[F(x)=\frac{1}{1-x} \]这就是 \(F(x)\) 的封闭形式。
我们也可以类似地算出 \(a=\langle1,p,p^2\dots\rangle\) 的生成函数的封闭形式，为：\(F(x)=\dfrac{1}{1-px}\)。
写一下 oiwiki 上的小练习：
- \(a=\langle0,1,1,\dots\rangle\)
幂级数：\(F(x)=\sum\limits_{i\ge 1}x^i\)
封闭形式：\(F(x)=\dfrac{x}{1-x}\)
- \(a=\langle1,0,1,0,1,\dots\rangle\)
幂级数：\(F(x)=\sum\limits_{i=0}\dfrac{(-1)^{i}+1}{2}x^i\)
封闭形式：\(F(x)=\dfrac{1}{1-x^2}\)
- \(a=\langle1,2,3,4,\dots\rangle\)
幂级数：\(F(x)=\sum\limits_{i=0}(i+1)x^i\)
封闭形式：\(F(x)=\dfrac{1}{(1-x)^2}\)
- \(a=\langle C_m^n \rangle\)，其中 \(m\) 为常数
幂级数：\(F(x)=\sum\limits_{i=0}^m C_m^{i} x^i\)
封闭形式：\(F(x)=(x+1)^m\) （二项式定理）
- \(a=\langle C_{m+n}^{n} \rangle\)，其中 \(m\) 为常数
幂级数：\(F(x)=\sum\limits_{i=0}C_{m+i}^{i}x^i\)
封闭形式：\(F(x)=\dfrac{1}{(1-x)^{m+1}}\)
我们有：\((1-x)F(x)=\sum\limits_{i=0}C_{m-1+i}^ix^i\)（手玩一下）
于是：\((1-x)^2F(x)=\sum\limits_{i=0}C_{m-2+i}^{i}x^i\)
\((1-x)^mF(x)=\sum\limits_{i=0}C_{m-m+i}^{i}x^i=\sum\limits_{i=0}x^i=\dfrac{1}{1-x}\)
于是 \(F(x)=\dfrac{1}{(1-x)^m}\)
我们约定 \(a \xrightarrow{\bf OGF} F(x)\) 表达序列 \(a\)（或者展开形式 \(a\)）的 OGF 的封闭形式为 \(F(x)\)。
常见的封闭形式：
\[\begin{aligned}&\langle1,1,1,\dots\rangle \xrightarrow{\bf OGF} \frac{1}{1-x}\\&\langle1,a,a^2,a^3\dots\rangle \xrightarrow{\bf OGF} \frac{1}{1-ax}\\&\sum\limits_{x=0}x^{ik} \xrightarrow{\bf OGF} \frac{1}{1-x^k}\\&\sum\limits_{x=0}c^ix^{ik} \xrightarrow{\bf OGF} \frac{1}{1-cx^k}\\&\left\langle\dbinom{n}{0},\dbinom{n}{1},\dbinom{n}{2},\dbinom{n}{3},\dots,\dbinom{n}{n} \right\rangle\xrightarrow{\bf OGF}(1+x)^n\\&\left\langle\dbinom{n}{0},-\dbinom{n}{1},\dbinom{n}{2},-\dbinom{n}{3},\dots,(-1)^n\dbinom{n}{n} \right\rangle\xrightarrow{\bf OGF}(1-x)^n\\&\left\langle\dbinom{n}{0},\dbinom{n+1}{1},\dbinom{n+2}{2},\dots \right\rangle\xrightarrow{\bf OGF}\frac{1}{(1-x)^{n+1}}\\&\left\langle0,1,\frac{1}{2},\frac{1}{3}\dots\right\rangle \xrightarrow{\bf OGF}\ln \frac{1}{1-x}=-\ln(1-x)\\&\left\langle0,1,\frac{1}{2!},\frac{1}{3!}\dots\right\rangle \xrightarrow{\bf OGF} e^x\end{aligned} \]斐波那契数列的生成函数
我们令 \(a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}\)，于是有：
\[\begin{aligned} &F(x)=a_0x^0+&a_1x^1+&a_2x^2+\dots \\x&F(x)= &a_0x^1+&a_1x^2+\dots \\x^2&F(x)= &&a_0x^2+\dots \end{aligned}\]故：
\[(1-x-x^2)F(x)=a_0x^0+(a_1-a_0)x=x \]于是有：\(F(x)=\dfrac{x}{1-x-x^2}\)。
一般来说，封闭形式有两种作用：求递推式或通项。
我们尝试通过斐波那契数列的封闭形式求得其通项。
观察发现分母是二次的，于是我们据此，设一个待定系数方程：
\[\frac{A}{1-ax}+\frac{B}{1-bx}=\frac{x}{1-x-x^2} \]通分，有：
\[\frac{A-Abx+B-Bax}{1-(a+b)x+abx^2}=\frac{x}{1-x-x^2} \]于是有：
\[\begin{cases} A+B=0 \\-Ab-Ba=1 \\a+b=1 \\ab=-1 \end{cases}\]通过这个可以解出 \(a,b,A,B\)：
\[\begin{cases} A=\dfrac{1}{\sqrt 5} \\B=-\dfrac{1}{\sqrt 5} \\a=\dfrac{1+\sqrt 5}{2} \\b=\dfrac{1-\sqrt 5}{2} \end{cases}\]我们解出来 \(a,b,A,B\) 有什么用呢？注意到我们有：
\[F(x)=\frac{A}{1-ax} + \frac{B}{1-bx} \]若 \(G(x)=\dfrac{A}{1-ax}\)，则有 \((1-ax)G(x)=A\)
于是我们就能容易地得到 \(G(x)\) 的展开形式： \(G(x)=\sum\limits_{i=0}Aa^ix^i\)
这样我们 \(F(x)\) 的展开形式就有了：
\[F(x)=\sum\limits_{i=0}(Aa^i+Bb^i)x^i \]把 \(a,b,A,B\) 带入，有：
\[F(x)=\sum\limits_{i=0}x^i\frac{1}{\sqrt 5}\left( \big(\frac{1+\sqrt 5}{2}\big)^i- \big(\frac{1-\sqrt 5}{2}\big)^i\right) \]这样我们就求出其通项了！！！
牛顿二项式定理
又称扩展二项式定理。
这个东西可以方便我们通过封闭形式求展开形式。
我们重定义组合数：
\[\dbinom{r}{k}=\frac{r^{\underline{k}}}{k!} \]其中 \(r\in\mathbb{C},k\in\mathbb{N}\)
于是对于 \(\alpha\in \mathbb{C}\)，我们有：
\[(1+x)^\alpha=\sum\limits_{n\ge0} \dbinom{\alpha}{n}x^n \]应用
两个 OGF 相乘是其卷积，组合意义是顺序拼接。
举个例子：
1. 付钱问题
我们有面额为 \(2,3,5\) 的硬币，每种都能无限使用，求用这些硬币付 \(n\) 元钱的方案。
我们设数列 \(a\)，\(a_n\) 表示用面额为 \(2\) 的硬币拼成 \(n\) 元的方案数。
显然有 \(a=\langle1,0,1,0,1,0\dots\rangle\)
类似地，我们定义出 \(b,c\) 为 \(3,5\) 元的方案数。
如果 \(a\) 的 OGF 为 \(F_a(x)\)，\(b\) 的 OGF 为 \(F_b(x)\)，考虑 \(F_a(x)F_b(x)\) 的 \(n\) 次项系数：
\[\sum\limits_{i=0}^na_ib_{n-i} \]表达的含义就是 \(i\) 元钱用 \(2\) 来拼，\(n-i\) 元钱用 \(3\) 来拼，方案数相乘。
很显然这个系数就是用 \(2,3\) 拼成 \(n\) 的方案数。
这样我们就能够理解：\(F_a(x)F_b(x)F_c(x)\) 的 \(n\) 次项系数就是问题索求。
2.P6078 [CEOI2004] Sweets
本题利用牛顿二项式定理推式子。
有 \(n\) 堆糖果，第 \(i\) 堆里面有 \(m_i\) 个。一共要吃 \(a\le x\le b\) 个糖，求方案数。
对于第 \(i\) 堆，我们考虑序列 \(p_i=\langle1,1,\dots,1\rangle\)，\(p_{i,j}\) 表示在第 \(i\) 堆糖果里吃 \(j\) 个的方案数，显然为 \(1\)。
我们有 \(p_i\) 的生成函数：\(F_i(x)=\sum\limits_{j=0}^{m_i}x^j=\dfrac{1-x^{m_i+1}}{1-x}\)。
因此第 \(k\) 项系数表示从所有的糖中吃 \(k\) 个的方案数的生成函数 \(G(x)\) 为：
\[G(x)=\prod\limits_{i=1}^{n}F_i(x)=(1-x)^{-n}\prod\limits_{i=1}^{n}(1-x^{m_i+1}) \]于是原问题就变成了求 \(\sum\limits_{i=a}^{b}[x^i]G(x)\)，或者说 \(G(x)\) 的 \(a\) 次项系数到 \(b\) 次项系数的和。
由于 \(n\le 10\)，我们对 \(\prod\limits_{i=1}^{n}(1-x^{m_i+1})\) 直接暴力展开，会有至多 \(2^n\) 项。
我们对 \((1-x)^{-n}\) 使用牛顿二项式定理：
\[(1-x)^{-n}=\sum\limits_{i\ge0}\dbinom{-n}{i}(-x)^i \]把这个广义组合数拆开，有：
\[\sum\limits_{i\ge0}\frac{(-n)(-n-1)\dots(-n-i+1)}{i!}(-x)^i \]当 \(i\) 为偶数时，\((-x)^i=x^i\)，我们对这个分数的分子每一项都取相反数，为：
\[\sum\limits_{i\ge0}\frac{(n)(n+1)\dots(n+i-1)}{i!}x^i \]不难发现这个就是：
\[\sum\limits_{i\ge0}\dbinom{n+i-1}{i}x^i \]当 \(i\) 为奇数时，\((-x)^i=-x^i\)，还是对分子每一项取相反数，但多一个负号：
\[\sum\limits_{i\ge0}\frac{-(n)(n+1)\dots(n+i-1)}{i!}\cdot(-x^i) \]两个负号抵消，又变回了：
\[\sum\limits_{i\ge0}\dbinom{n+i-1}{i}x^i \]于是我们有：
\[(1-x)^{-n}=\sum\limits_{i\ge0}\dbinom{n+i-1}{i}x^i \]考虑 \(\prod\limits_{i=1}^{n}(1-x^{m_i+1})\) 的某一项 \(x^k\) 对答案的贡献，设 \(\prod\limits_{i=1}^{n}(1-x^{m_i+1})\) 中 \(x^k\) 的系数为 \(c^k\)，于是贡献为：
\[c_k\sum\limits_{i=a-k}^{b-k}\dbinom{n-1+i}{i}=c_k\left(\dbinom{n+b-k}{b-k} - \dbinom{n+a-k-1}{a-k-1}\right) \]然后 \(O(b)\) 求答案。
复杂度为 \(O(2^n\cdot b)\)。
关于上式的证明，其实就是在证：
\[\sum\limits_{i=l}^{r}\dbinom{n-1+i}{i}=\dbinom{n+r}{r}-\dbinom{n+l-1}{l-1} \]即证：
\[\sum\limits_{i=0}^{m}\dbinom{n+i}{i}=\dbinom{n+m+1}{m} \]画个杨辉三角，癔症。
当然因为这个逆天模数不是质数，我们要想想怎么求组合数。
注意到我们求的组合数都是 \(\dbinom{n+p}{p}\) 形式的，它等于：
\[\frac{(n+p)!}{n!\cdot p!}=\frac{(p+1)\times\dots\times(n+p)}{n!} \]我们发现 \(n!\) 很小，于是我们可以对分子取模 \(2004\times n!\)，然后再除以 \(n!\) 后再模 \(2004\) 即可。
这样这个题就做完了。
3.P4451 [国家集训队] 整数的lqp拆分
本题运用类似斐波那契数列通项公式的推法来推通项。
简述题意：给定 \(n\)，求对于每一种 \(n\) 的拆分（记为 \(a_1\dots a_m\)，其中 \(1\le m,a_i\le n\)），求和 \(\prod\limits_{i=1}^{m}Fib_{a_i}\)
其中 \(Fib_i\) 为斐波那契数列第 \(i\) 项；\(Fib_0=0,Fib_1=1\)。
由于对生成函数不熟悉，我们慢慢推一下东西。
先考虑只把 \(n\) 拆成两个数，我们如何对于每一种拆分方案，计算贡献之和。
我们记斐波那契数列 \(\langle0,1,1,2,3,5,\dots\rangle\) 的生成函数为 \(F(x)\)。
仔细一想，会发现 \([x^n]F(x)^2\) 就是我们要求的贡献之和。根据卷积，它就是：\(\sum\limits_{i=0}^{n}Fib_i\cdot Fib_{n-i}\)。这里 \(i\) 枚举了拆分方案，卷积求了和。
进而，我们如果把 \(n\) 拆成 \(m\) 个数，贡献之和就是 \([x^n]F(x)^m\)。
由于题目没说分成几个数，于是我们要枚举 \(m\)，于是答案为：
\[\sum\limits_{i=1}^{n}[x^n]F(x)^i \]由于不同项系数互不影响，我们就可以写作：
\[[x^n]\sum\limits_{i=1}^{n}F(x)^i \]我们考虑把后面的东西写成一个关于 \(F(x)\) 的生成函数形式。
首先，这里的上界显然可以换成 \(\infty\)，因为次数大于 \(n\) 时不会对 \(x^n\) 项系数产生影响。
于是我们令 \(G(x)=\sum\limits_{i\ge 1}F(x)^i\)。
因为我们知道 \(\sum\limits_{i\ge 1}x^i=\dfrac{x}{1-x}\)（oiwiki 小练习1）
所以我们有：
\[G(x)=\frac{F(x)}{1-F(x)} \]把 \(F(x)=\dfrac{x}{1-x-x^2}\) 带入，化简得：
\[G(x)=\frac{x}{1-2x-x^2} \]类似斐波那契数列，我们设：
\[\frac{A}{1-ax}\cdot\frac{B}{1-bx}=\frac{x}{1-2x-x^2} \]通分，有：
\[\frac{A-Abx+B-Bax}{1-(a+b)x+abx^2}=\frac{x}{1-2x-x^2} \]于是有：
\[\begin{cases} A+B=0 \\-Ab-Ba=1 \\a+b=2 \\ab=-1 \end{cases}\]通过这个可以解出 \(a,b,A,B\)：
\[\begin{cases} A=\dfrac{\sqrt 2}{4} \\B=-\dfrac{\sqrt 2}{4} \\a=1+\sqrt 2 \\b=1-\sqrt 2 \end{cases}\]我们有：
\[G(x)=\sum\limits_{i=0}(Aa^i+Bb^i)x^i \]把 \(a,b,A,B\) 带入，有：
\[G(x)=\sum\limits_{i=0}x^i\frac{\sqrt 2}{4}\left( (1+\sqrt 2)^i- (1-\sqrt 2)^i\right) \]由于我们要求的答案为 \([x^n]G(x)\)，也就是：
\[[x^n]G(x)=\frac{\sqrt 2}{4}\left((1+\sqrt 2)^n-(1-\sqrt 2)^n\right) \]奇波拉求一下 \(\sqrt 2\)，带入并快速幂就行了。
4. UVA12298 Super Poker II
这题的解法在多项式习题中详细解释了。
为什么放在这里？四个数列 \(p_1\sim p_4\) 的卷积其实就是在跑一个背包。相应的，从生成函数之积理解，就代表了一种拼接的过程，对应了 OGF 的组合意义。（？）
这题也为我们提供了一种把题目向多项式和生成函数转化的思路。
4.5.CF632E Thief in a Shop（和一点心得）
这些是心得：
假如说我们有一个长度为 \(n\) 的数组 \(c\)。
我们有这么一种构造方式，类似于背包：
构造序列 \(a\)，使得 \(a_{c_i}=1\)，其他位置为 \(0\)，\(i\in[1,n]\)。
如果我们求出 \(a\) 的生成函数 \(F(x)=\sum x^{c_i}\)，则 \([x^t]F(x)^k\) 表达的含义为：用 \(k\) 个数，拼成 \(t\)，且顺序不同的方案数。
也就是说，我们每次多乘一个 \(F(x)\)，就像是发生了一次 dp 转移，使得我们可以多使用一个数。
有一道练习题，标题上就说了。
只需要用和心得相同的方式构造 \(F(x)\)，求 \(F(x)^k\) 不为 \(0\) 的项输出项的编号即可。
这个题有专门对 \(998244353\) 和 \(1004535809\)的 hack 数据，所以我选择了原根为 \(31\) 的模数 \(2013265921\)，这个没人卡！
4.75.BZOJ3771. Triple
你应该把这个题放在 CF632E Thief in a Shop 后面。——Qcfff
给定 \(n\) 个不同的 \(a_i\)，求选 \(1\) 或 \(2\) 或 \(3\) 个能组成多少种权值，以及每种权值有多少种方案。
首先 OGF，构造：
\[F(x)=\sum\limits x^{a_i} \]然后我们求出 \(G(x)=F(x)^2\)，\(H(x)=F(x)^3\)。
但我们不能简单的把 \(F\)，\(G\)，\(H\) 对应项系数相加，因为这样既会算重复的，又会算不同排列。怎么办呢？
构造：
\[A(x)=\sum x^{2a_i},B(x)=A(x)F(x),C(x)=\sum x^{3a_i} \]拿样例举例：五种权值为 \(5,6,7,8,9\)，考虑 \(16\) 的构造。
容易发现，\(\dfrac{G(x)-A(x)}{2}\) 就是两把斧子。减掉 \(A(x)\) 表示把 \(16=8+8\) 构成的情况去掉，除以 \(2\) 表示废掉 \((7,9)\) 和 \((9,7)\) 之一，只保留一个。
然后 \(\dfrac{H(x) - 3\times \Big(B(x)-C(x)\Big) -C(x)}{6}\) 是三把斧子。
\[18=6+6+6=5+5+8=5+6+7 \]\(B(x)\) 会统计以下结果：\(([5,5],8),([6,6],6)\)。
\(C(x)\) 会统计以下结果：\((6,6,6)\)。
\(B(x)-C(x)\) 相当于排除掉 \((6,6,6)\) 这种组合，再乘以 \(3\) 表达 \((5,5,8),(5,8,5),(8,5,5)\) 均在 \(H(x)\) 中统计，所以都要去掉。
减去 \(C(x)\) 表达把 \((6,6,6)\) 减去。最后除以 \(6\) 表达废掉 \((5,6,7),(5,7,6),(6,5,7),(6,7,5),(7,5,6),(7,6,5)\) 之五，只保留一个。
最后记得：
宝玉亦暇，好事多“模”
4.875.BZOJ3513. idiots
给 \(n\) 个木棒，随机选出三根，求能围成三角形的概率。
全程没有一点自己的思考，对着 Qcf 照搬。
由于木棒有重复，我们考虑 \(t_i\) 表示长度为 \(i\) 的木棒的出现次数。
构造生成函数 \(F(x)=\sum x^{t_i}\)
运用和上一道例题相似的办法，令 \(A(x)=\sum x^{2t_i}\)，则 \(\dfrac{F(x)^2-A(x)}{2}\) 就是用两根不相同的木棒拼成 \(i\) 的方案数。
然后尝试统计，发现正着很难，于是正难则反，考虑统计围不成三角形的概率。
围不成三角形等同于两边之和小于等于第三边，于是我们枚举第三遍，只需要使两边之和小于等于它就行了。也就是：
\[\sum\limits_{i=0}^{\max(a)}t_i\sum\limits_{j=1}^{i}[x^j]\dfrac{F(x)^2-A(x)}{2} \]后者显然前缀和，这个就能 \(O(n)\) 算了。
记得除以 \(\dbinom{n}{3}\) 后再用 \(1\) 去减，算出能围成的概率。
4.9375.P3321 [SDOI2015] 序列统计
这个序号没完了是吧。
给了素数 \(m\)，和一个互不相同的，元素均小于 \(m\) 的集合 \(S\)，考虑构造一个长度为 \(n\) 的序列，满足：
- 序列的元素均属于 \(S\)。
- 序列的每一项之积为 \(X\)。
其中 \(X\) 给定，求这样的序列个数。
我们记集合大小为 \(|S|\)。
那么我们可以列出一个式子：
\[S_1^{a_1}\cdot S_2^{a_2}\cdots S_{|S|}^{a_{|S|}}\equiv X\pmod m \]我们要构造出一组 \(a\)，保证 \(\sum a=n\)，且上述式子成立。
然后看了题解，发现这个题和离散对数有关！！！
所以我们找到模 \(m\) 的原根 \(g\)。根据原根的知识，若 \(\gcd(a,m)=1\)，则 \(g^x\equiv a\pmod m\) 一定有解。
于是我们可以设 \(S_i\equiv g^{k_i}\pmod m\)，\(X\equiv g^{K}\pmod m\)
则原式变为：
\[g^{\sum\limits_{i=1}^{|S|}a_ik_i}\equiv g^{K}\pmod m \]于是有：
\[\sum\limits_{i=1}^{|S|}a_ik_i\equiv K\pmod {\varphi(m)} \]这个东西相当于在说：从 \(|S|\) 个物品中选出 \(n\) 个，可以重复选，求出它们的和在模 \(m\) 的意义下与 \(K\) 同余。
然后就变成了生成函数的题！
我们构造 OGF：\(F(x)=\sum x^{k_i}\)
求出 \(F(x)^n\) 的第 \(K\) 项，第 \(K+\varphi(m)\) 项，第 \(K+2\varphi(m)\) 项……系数之和就行了。
首先，我们快速幂不能 \(\ln\exp\)，因为常数项不为 \(1\)，不方便，而这个题时限允许我们用倍增快速幂。
我们在每次多项式乘法后，进行如下操作：
对所有的 \(i\ge \varphi(m)\)，执行 \(f_{i\bmod \varphi(m)} \leftarrow f_{i\bmod \varphi(m)}+f_i\)，然后 \(f_i\leftarrow 0\)。
容易证明这对快速幂不影响。这样子操作后，我们只需要输出答案的 \(K\bmod \varphi(m)\) 项系数就行了。
这大缝合怪只评紫？
5.CF438EThe Child and Binary Tree
毕竟是学习中，看题解不可耻（心虚）
这题是个 dp。没想出来咋 dp。
我们设 \(f_x\) 表示权值为 \(x\) 的二叉树个数。
\(g_x=[x\in c]\)，即如果 \(x\) 为 \(c\) 数组中的某一个，那么 \(g_x=1\)，否则 \(g_x=0\)。
我们可以写出 \(f\) 的转移：
\[f_n=\begin{cases} 1 & n=0\text{ or }n=1 \\ \sum\limits_{i=0}^{n}g_i\sum\limits_{j=0}^{n-i}f_{j}f_{n-i-j} &\text{otherwise} \end{cases}\]表达的含义为：枚举根为 \(i\)，左子树权值为 \(j\)，右子树权值为 \(n-i-j\) 的情况。
如果我们记 \(f\) 的生成函数为 \(F(x)\)，\(g\) 的生成函数为 \(G(x)\)，那么下面式子表达的就是：
\[\begin{aligned} F(x)&=\sum\limits_{n=0}f_nx^n \\&=f_0x^0+\sum\limits_{n\ge1}x^n\sum\limits_{i=0}^{n}g_i\sum\limits_{j=0}^{n-i}f_{j}f_{n-i-j} \end{aligned}\]为了化为卷积形式，我们刻意让后面对 \(n\) 的枚举从 \(0\) 开始！这样做不会影响结果，于是（\(f_0x^0=1\)）：
\[F(x)=1+\sum\limits_{n=0}x^n\sum\limits_{i=0}^{n}g_i\sum\limits_{j=0}^{n-i}f_{j}f_{n-i-j} \]此时就会发现后面的式子就是 \(G(x)F(x)^2\)，于是得出：
\[F(x)=1+G(x)F(x)^2 \]解一元二次方程，有：
\[F(x)=\frac{1\pm \sqrt{1-4G(x)}}{2G(x)} \]有两个解，咋办捏？（下面内容引自九阳哥博客）
把 \(x=0\) 带入（我不太理解对于一个值没有意义的生成函数，把一个值带进去有何意义？），应有 \(F(0)=f_0=1\)，\(G(x)=0\)。
于是会有方程 \(1=\dfrac{1\pm 1}{0}\)。当取正号时，右边趋于正无穷，矛盾；所以只能取负号，这里分子分母都有 \(0\)，约了（？？？好逆天）
所以我们就有：
\[F(x)=\frac{1-\sqrt{1-4G(x)}}{2G(x)}=\frac{}{}\frac{2}{1+\sqrt{1-4G(x)}} \]套个多项式板子整整就行了。啊？
6.P4389 付公主的背包
还是抄题解。
根据例题一付钱问题，我们很容易把背包转化成如下形式：
有 \(n\) 个数列，其生成函数为 \(F_j(x)=\sum\limits_{i=0}x^{iv_j}\)
有 \(G(x)=\prod\limits_{i=1}^{n}F_i(x)\)
输出 \(G(x)\) 的 \(1\sim m\) 项即可。
暴力背包转移寄掉。易得 \(F_i(x)\) 的封闭形式：
\[F_i(x)=\frac{1}{1-x^{v_i}} \]于是我们有：
\[G(x)=\frac{1}{\prod\limits_{i=1}^{n}(1-x^{v_i})} \]复杂度 \(O(2^n)\) 更慢了！
于是来了很牛逼的一步：我们把乘积转化成指数相加。具体的，我们设 \(A_i(x)=1-x^{v_i}\)，\(B(x)=\prod\limits_{i=1}^{n}A_i(x)\)
于是会有：
\[B(x)=\prod\limits_{i=1}^{n}\mathrm{e}^{\ln A_i(x)}=\mathrm{e}^{\sum\limits_{i=1}^{n}\ln A_i(x)} \]我们思考 \(\ln A_i(x)\) 怎么求。
我们设 \(\ln A_i(x)=H(x)\)
两边对 \(x\) 求导，有（左式可参见多项式 \(\ln\) 的推导过程）：
\[\frac{A_i'(x)}{A_i(x)}=H'(x) \]因为 \(A_i(x)=1-x^{v_i}\)，于是 \(A_i'(x)=-v_ix^{v_i-1}\)，故：
\[\frac{-v_ix^{v_i-1}}{1-x^{v_i}}=H'(x) \]将 \(-v_ix^{v_i-1}\) 提出来，后面的东西可以从封闭形式转化成展开形式：
\[-v_ix^{v_i-1}\sum\limits_{j=0}x^{jv_i}=H'(x) \]再把外面的项乘进去：
\[-\sum\limits_{j=0}v_ix^{jv_i+v_i-1}=H'(x) \]两边同时积分，由于 \(ax^{b}\) 积分的结果为 \(\dfrac{a}{b+1}x^{b+1}\)，于是有（积分对加法有没有分配律我也不到）：
\[-\sum\limits_{j=0}\frac{v_i}{jv_i+v_i}x^{jv_i+v_i}=H(x)=\ln A_i(x) \]左边太丑了，化简它！显然可以约分：
\[-\sum\limits_{j=0}\frac{1}{j+1}x^{v_i(j+1)}=\ln A_i(x) \]发现都是 \(j+1\)，于是我们 \(j\) 从 \(1\) 开始枚举：
\[-\sum\limits_{j=1}\frac{1}{j}x^{jv_i}=\ln A_i(x) \]我们要求的就是：
\[\sum\limits_{i=1}^{n}\ln A_i(x)=-\sum\limits_{i=1}^{n}\sum\limits_{j=1}\frac{1}{j}x^{jv_i} \]要找到这个多项式在 \(1\sim m\) 次项系数。
如果 \(v_i\) 相同，提供的贡献也是相同的，于是可以把 \(v_i\) 的出现次数存起来。
直接枚举互不相同的 \(v_i\)，然后 \(j\le \dfrac{m}{v_i}\) 时才会有贡献。复杂度是调和级数了，为 \(O(m\log m)\)。
求出这个，\(\exp\) 一下，求一下逆就行了。
EGF 指数生成函数
定义为形式幂级数：
\[\hat F(x)=\sum\limits_{i=0}a_i\frac{x^i}{i!} \]可以理解为序列 \(\langle\dfrac{a_i}{i!}\rangle\) 的 OGF。
封闭形式
对于序列 \(a=\langle1,1,1,\dots\rangle\)，我们有其封闭形式：
\[\hat F(x)=\mathrm{e}^x \]把 \(\mathrm{e}^x\) 泰勒展开就行。
我们列出几个常见的 EGF 封闭形式：
\[\begin{aligned} &\langle1,1,1,\dots\rangle \xrightarrow{\bf EGF} \mathrm{e}^x \\&\langle1,p,p^2,\dots\rangle \xrightarrow{\bf EGF} \mathrm{e}^{px} \\&\langle1,-1,1,-1,\dots\rangle \xrightarrow{\bf EGF} \mathrm{e}^{-x} \\&\langle1,0,1,0,\dots\rangle \xrightarrow{\bf EGF} \frac{\mathrm{e}^x+\mathrm{e}^{-x}}{2} \\&\langle0,1,0,1,\dots\rangle \xrightarrow{\bf EGF} \frac{\mathrm{e}^x-\mathrm{e}^{-x}}{2} \end{aligned}\]基本运算
- 加减和 OGF 相同，我们考虑卷积。
对于两个序列 \(a,b\)，设它们的 EGF 分别为 \(\hat F(x),\hat G(x)\)，则：
\[\begin{aligned} \hat F(x) \hat G(x)&=\sum\limits_{n=0}x^n\sum\limits_{i=0}^{n}\frac{a_ib_{n-i}}{i!(n-i)!} \\&=\sum\limits_{n=0}\frac{x^n}{n!}\sum\limits_{i=0}^{n}\dbinom{n}{i}a_ib_{n-i} \end{aligned}\]也就是说 \(\hat F(x)\hat G(x)\) 是序列 \(\left\langle\sum\limits_{i=0}^{n}\dbinom{n}{i}a_ib_{n-i}\right\rangle\) 的 EGF。
注意第 \(n\) 项系数 \(\sum\limits_{i=0}^{n}\dbinom{n}{i}a_ib_{n-i}\)，代表的是把 \(n\) 个有标号的元素，选 \(i\) 个分配给 \(a\)，剩余的 \(n-i\) 个分配给 \(b\)。
这意味着 EGF 的积的组合意义是有标号的拼接（我也看不懂……）。
还有一种理解：把两个部分“归并”，不同的方案数也是上式。比如：
OGF：{AAAA}×{BBB}={AAAABBB}，无标号的直接拼接。
EGF：{AAAA}×{BBB}={ABBAABA},{BAABAAB},{BBABAAA}...共 \(\dbinom{7}{3}\) 种方案。
- 还有一个重要性质：对于 EGF \(\hat F(x)\)，考虑 \(\mathrm{e}^{\hat F(x)}\) 的含义。
根据 \(\mathrm{e}^x\) 的麦克劳林级数定义（或者理解为 \(\langle1,1,1,\dots\rangle\) 的封闭形式），有：
\[\mathrm{e}^{\hat F(x)}=\sum\limits_{i=0}\frac{\hat F(x)^i}{i!} \]\(\hat F(x)^i\) 表示把 \(i\) 个集合拼在一起，除以 \(i!\) 相当于把集合间的先后顺序废掉，所以如果 \(\hat F(x)\) 为单个部分的 EGF，那么 \(e^{\hat F(x)}\) 就是若干个相同部分组成的整体的 EGF。
这几段话我是一点都看不懂。不做题根本不理解这是在说什么。淦。
例题
看些例题吧。
记得一般我们把 EGF 当做 OGF 算，所以最后要乘个阶乘！
1.「染色问题」
用红绿蓝三种颜色染一个长为 \(n\) 的纸条，要求红色和绿色分别的出现次数只能偶数次。
我们不妨先看一下只用一种颜色染满纸条会是什么样。
于是我们对三个颜色分别构造数列 \(r,g,b\)。某个数列的第 \(k\) 项表示只用这一种颜色染满纸条的方案数。
显然有 \(r=g=\langle1,0,1,0,\dots\rangle\)，\(b=\langle1,1,1,1,\dots\rangle\)
令这三个序列的 EGF 分别为：\(\hat F_r(x),\hat F_g(x),\hat F_b(x)\)。
显然有 \(\hat F_r(x)=\hat F_g(x)=\dfrac{e^x+e^{-x}}{2}\)，\(\hat F_b(x)=e^x\)
我们考虑某两个 EGF 的乘积。比如说 \(\hat F_r\) 和 \(\hat F_g\)
这相当于把纯红色的纸带和纯绿色的纸带，“归并”成一个红绿相间的纸带。
因为 \([x^n](\hat F_r(x)\hat F_g(x))=\sum\limits_{i=0}^{n}\dbinom{n}{i}r_ig_{n-i}\)，多乘一个组合数就刚好枚举了红绿交替的情况。
这样子我们就能理解 \(\hat F_r(x)\hat F_g(x)\) 的实际含义了！它的第 \(n\) 项系数表达的，正是一条红绿相间的纸带有多少种方案！
于是我们再乘上 \(\hat F_b(x)\)，就有了红绿蓝相见的纸带方案数了！
\[\hat F_r(x)\hat F_g(x)\hat F_b(x)=\left(\frac{e^x+e^{-x}}{2}\right)^2e^x=\frac{e^{3x}+2e^x+e^{-x}}{4} \]提取第 \(n\) 项系数就行：
\[\frac{3^n+2\cdot 1^n+(-1)^n}{4} \]2. P5339 [TJOI2019] 唱、跳、rap和篮球
抄题解。
设 \(f(k)\) 表示钦定 \(k\) 组，剩余的随意排列的方案数。
\(g(k)\) 表示一共有 \(k\) 组的方案数。
于是有 \(f(k)=\sum\limits_{i=k}\dbinom{i}{k}g(k)\)，意义为枚举一共有 \(i\ge k\) 组，我们钦定这 \(i\) 组中的 \(k\) 个，共有 \(\dbinom{i}{k}\) 种钦定方式。
有一个二项式反演，我不会，但能得出以下结论：
\[g(k)=\sum\limits_{i=k}(-1)^{i-k}\dbinom{i}{k}f(i) \]我们要求的是 \(g(0)\)，也就是没有唱跳 rap 篮球组合的方案。
把 \(k=0\) 带入上式，有：
\[g(0)=\sum\limits_{i=0}(-1)^if(i) \]因为当 \(k=0\) 时，\(\dbinom{i}{k}=1\)。
我们考虑 \(f(k)\) 怎么求。
设 \(S(a,b,c,d,n)\) 表示最多 \(a\) 个唱，\(b\) 个跳，\(c\) 个 rap，\(d\) 个篮球，队里头最多放 \(n\) 个人，任意排列的方案数。
对于 \(f(k)\)，我们把原本的 \(k\) 组分别缩成一个整体，这样子队伍中只剩下 \(n-3k\) 个人。我们选出 \(k\) 个位置来放这 \(k\) 个整体，选法为 \(\dbinom{n-3k}{k}\)。
选好了 \(k\) 组人的位置，剩余的位置可以随便填。剩下的位置共有 \(n-4k\) 个，四种人各自少了 \(k\) 个，于是方案数为 \(S(a-k,b-k,c-k,d-k,n-4k)\)。
所以我们有：
\[f(k)=\binom{n-3k}{k}S(a-k,b-k,c-k,d-k,n-4k) \]带入 \(g(0)\) 的式子，有：
\[g(0)=\sum\limits_{k=0}(-1)^k\binom{n-3k}{k}S(a-k,b-k,c-k,d-k,n-4k) \]显然 \(k\le \dfrac{n}{3}\)，由于 \(n\le 10^3\)，于是我们先枚举 \(k\)，考虑 \(S(a-k,b-k,c-k,d-k,n-4k)\) 怎么求。
\(S(a,b,c,d,n)\) 的组合意义是：用四种有个数限制的颜色，涂满一个长度为 \(n\) 的纸带。这正好是例题1染色问题！
转化成 EGF 就能 \(O(n\log n)\) 求 \(S\) 了。这样总复杂度是 \(O(n^2\log n)\)。比较慢，能优化。
把 EGF 式子写开看看，我们把四种人的生成函数分别记作 \(\hat F_{1\sim 4}(x)\)。
于是乎我们有：
\[\hat F_1(x)=\sum\limits_{i=1}^{a-k}\frac{x^i}{i!} \]\[\vdots \]\[\hat F_4(x)=\sum\limits_{i=1}^{d-k}\frac{x^i}{i!} \]这样我们要求的答案就是 \([x^{n-4k}]\hat F_1(x)\hat F_2(x)\hat F_3(x)\hat F_4(x)\)。
我们考虑先求出 \(\hat F_1(x)\hat F_2(x)\) 和 \(\hat F_3(x)\hat F_4(x)\) 的 \(x^0\sim x^{n-4k}\) 项，然后可以直接算答案。
我们从大到小枚举 \(k\)，这样的话我们四个生成函数的上界每次只会增加 \(1\)，可以优化计算。、
\(k\) 的最大值为 \(k_0=\min(a,b,c,d,\dfrac{n}{4})\)。
我们先处理出 \(k=k_0\) 时 \(\hat F_1(x)\hat F_2(x)\) 和 \(\hat F_3(x)\hat F_4(x)\) 的结果，然后考虑上界增加 \(1\) （以 \(k_0\rightarrow k_0-1\) 来举例）时这两个会怎么变化。记上界变化后的生成函数为 \(\hat F'_i(x)\)，以 \(\hat F'_1(x)\hat F'_2(x)\) 来举例：
\[\begin{aligned} \hat F'_1(x)\hat F'_2(x)&=\Big(\hat F_1(x)+\frac{x^{a-k_0+1}}{(a-k_0+1)!}\Big)\Big(\hat F_2(x)+\frac{x^{b-k_0+1}}{(b-k_0+1)!}\Big) \\&=\hat F_1(x)\hat F_2(x)+\frac{x^{a-k_0+1}}{(a-k_0+1)!} \hat F_2(x)+\frac{x^{b-k_0+1}}{(b-k_0+1)!}\hat F_1(x)+\frac{x^{(a-k_0+1)+(b-k_0+1)}}{(a-k_0+1)!(b-k_0+1)!} \end{aligned}\]第一项算过了，第二三项可以 \(O(n)\) 算，最后一项 \(O(1)\) 算。
这样就行了。
3. P5748 集合划分计数
求将 \(n\) 个不同的球放进若干个相同盒子的方案数。
这个题能够增进我对前文所述 \(\mathrm{e}^{\hat F(x)}\) 的理解。
假设只有一个盒子且必须放，我们构造数列 \(a=\langle0,1,1,1,\dots\rangle\)，它的第 \(n\) 项表达将 \(n\) 个不同的球放进一个盒子里的方案数。
由于我们盒子必须放东西，所以 \(a_0=0\)，后面会解释为什么要求必须放。
我们能求出 \(a\) 的 EGF：\(\hat F(x)=\sum\limits_{i\ge 1}\dfrac{x^i}{i!}=e^x-1\)。
如果两个相同的盒子且每个盒子至少一个球呢？它的生成函数为 \(\dfrac{F(x)^2}{2!}\)。
我们以第 \(n\) 项举例：\([x^n]\dfrac{F(x)^2}{2!}=\dfrac{1}{2}\sum\limits_{i=0}^{n}\dbinom{n}{i}a_ia_{n-i}\)。
因为球不同，我们枚举向第一个盒子放 \(i\) 个球，向第二个盒子放 \(n-i\) 个球后，还需要乘上一个组合数 \(\dbinom{n}{i}\) 表示选取哪些有标号的球！
再由于两个 \(F(x)\) 之间谁先放谁后放的先后顺序要废掉，所以除掉一个 \(2!\)。
或者说，\(F(x)^2\) 是两个不同的盒子的生成函数，除以 \(2!\) 后就变回了相同的盒子。
所以 \(\dfrac{F(x)^2}{2!}\) 就是两个相同的盒子且每个盒子至少一个球的生成函数！
我们要求的是若干个盒子，所以答案就是 \([x^n]\sum\limits_{i\ge 0}\dfrac{\hat F(x)^i}{i!}=\mathrm{e}^{\hat F(x)}=\mathrm{e}^{\mathrm{e}^x-1}\)。
这里为什么 \(i\) 可以从 \(0\) 开始？\(\hat F(x)^0\) 根本没有意义啊？其实这时候 \(\dfrac{\hat F(x)^0}{0!}=1\) 会加在常数项中，而常数项我们从来没有用过，所以加上去也无妨我们索求的答案！
多项式 \(\exp\) 就行了。
\[\begin{aligned}\\\\\\\\\\\\\\\\\\\\\\\end{aligned} \] 标签：frac,函数,limits,dfrac,sum,生成,hat,dbinom From： https://www.cnblogs.com/baoyangawa/p/18091100