普通生成函数（Ordinary Generating Function）

五个小练习：对于每个序列 $a$ 求出它的 OGF 封闭形式。

$\begin{aligned} a &= [0, 1, 1, 1, 1, \dots]\\ F(x) &= \sum_{i = 0}^\infty x^ia_i = \sum_{i = 1}^\infty x^i\\ F(x) - xF(x) &= x\\ (1 - x)F(x) &= x\\ F(x) &= \frac x{1 - x}\\ \end{aligned}$

$\begin{aligned} a &= [1, 0, 1, 0, 1, \dots]\\ F(x) &= \sum_{i = 0}^\infty x^ia_i = \sum_{i = 0}^\infty x^{2i} = \sum_{i = 0}^\infty (x^2)^i\\ F(x) - x^2F(x) &= 1\\ (1 - x^2)F(x) &= 1\\ F(x) &= \frac 1{1 - x^2}\\ \end{aligned}$

$\begin{aligned} a &= [1, 2, 3, 4, \dots]\\ F(x) &= \sum_{i = 0}^\infty x^ia_i = \sum_{i = 0}^\infty (i + 1)x^i\\ F(x) - xF(x) &= \sum_{i = 0}^\infty x^i\\ F(x) - xF(x) &= \frac 1{1 - x}\\ F(x) &= \frac 1{(1 - x)^2}\\ \end{aligned}$

$\begin{aligned} a_i &= \binom mi\\ F(x) &= \sum_{i = 0}^\infty x^ia_i\\ &= \sum_{i = 0}^m \binom mi x^i\\ &= \sum_{i = 0}^m \binom mi x^i 1^{m - i}\\ &= (x + 1)^m\\ \end{aligned}$

$\begin{aligned} a_{m, i} &= \binom{m + i}i\\ F_m(x) &= \sum_{i = 0}^\infty x^ia_{m, i}\\ &= \sum_{i = 0}^\infty x^i \binom {m + i}i\\ &= \sum_{i = 0}^\infty \sum_{j = 0}^i x^i \binom {m + j - 1}j\\ &= \sum_{i = 0}^\infty \sum_{j = 0}^\infty x^{i + j} \binom {m + j - 1}j\\ &= \left(\sum_{i = 0}^\infty x^i\right) \left(\sum_{j = 0}^\infty x^j \binom {m + j - 1}j\right)\\ &= \frac{F_{m - 1}(x)}{1 - x}\\ &= \frac1{(1 - x)^{m + 1}}\\ \end{aligned}\\$

现在我们考虑用生成函数推导斐波那契数列的通项：

$\begin{aligned} a_0 = 0, a_1 &= 1, a_i = a_{i - 1} + a_{i - 2}\\ F(x) &= \sum_{i = 0}^\infty x^ia_i\\ (1 - x - x^2)F(x) &= x\\ F(x) &= \frac x{1 - x - x^2}\\ \end{aligned}\\$

这样只是求出了封闭形式，但是这还不够，我们需要求出它每一项的系数。考虑把他给拆成两个等比数列的和，其中 $A, B$ 表示首项，而 $a, b$ 表示公比。

$\frac x{1 - x - x^2} = \frac A{1 - ax} + \frac B{1 - bx}$

通分：

$\because\frac x{1 - x - x^2} = \frac{A + B - Abx - Bax}{1 - ax - bx + abx^2}\\ \therefore\begin{cases} A + B = 0\\ Ab + Ba = -1\\ a + b = 1\\ ab = -1\\ \end{cases}\\ \because\begin{cases} a + b = 1\\ ab = -1 (a, b > 0)\\ \end{cases}\\ \therefore\ \begin{aligned} a - \frac 1a &= 1\\ a^2 - a - 1 &= 0\\ \end{aligned}\\ \therefore a = \frac{1 + \sqrt5}2, b = \frac{1 - \sqrt5}2\\ \because\begin{cases} A + B = 0\\ Ab + Ba = -1\\ \end{cases}\\ \therefore\ \begin{aligned} Ab - Aa &= -1\\ Aa - Ab &= 1\\ A(a - b) &= 1\\ A\sqrt5 &= 1\\ A &= \frac1{\sqrt5}\\ B &= -\frac1{\sqrt5}\\ \end{aligned}\\ \begin{cases} A = \frac1{\sqrt5}\\ B = -\frac1{\sqrt5}\\ a = \frac{1 + \sqrt5}2\\ b = \frac{1 - \sqrt5}2\\ \end{cases}$

最后我们可以把这个东西往回带并求出形式幂级数，从而得到每一项的系数，即通项。

$\begin{aligned} F(x) &= \sum_{i = 0}^\infty \frac1{\sqrt5}\left(\frac{1 + \sqrt5}2x\right)^i - \frac1{\sqrt5}\left(\frac{1 - \sqrt5}2x\right)^i\\ F(x) &= \sum_{i = 0}^\infty x^i \frac1{\sqrt5}\left(\left(\frac{1 + \sqrt5}2\right)^i - \left(\frac{1 - \sqrt5}2\right)^i\right)\\ \end{aligned}$

所以我们得到斐波那契数列的通项是 $Fib_i = \frac1{\sqrt5}\left(\left(\frac{1 + \sqrt5}2\right)^i - \left(\frac{1 - \sqrt5}2\right)^i\right)$。

食物

这个题显然可以暴力推生成函数，对于每个食物都构造出生成函数，乘起来就可以得到通项。

第一个：$\sum_{i = 0}^\infty x^{2i} = \dfrac 1{1 - x^2}$。

第二个：$\dfrac{1 - x^2}{1 - x}$。

第三个：$\dfrac{1 - x^3}{1 - x}$。

第四个：$\sum_{i = 0}^\infty x^{2i + 1} = \dfrac x{1 - x^2}$。

第五个：$\sum_{i = 0}^\infty x^{4i} = \dfrac 1{1 - x^4}$。

第六个：$\dfrac{1 - x^4}{1 - x}$。

第七个：$\dfrac{1 - x^2}{1 - x}$。

第八个：$\sum_{i = 0}^\infty x^{3i} = \dfrac 1{1 - x^3}$。

乘起来之后变成以下形式：

$\dfrac{x(1 - x^2)^2(1 - x^3)(1 - x^4)}{(1 - x)^4(1 - x^2)^2(1 - x^3)(1 - x^4)} = \dfrac x{(1 - x)^4}$

转化成展开形式：

$\sum_{i = 0}^\infty x^i \times x\binom{i + 3}i\\ \sum_{i = 1}^\infty x^i \binom{i + 2}{i - 1}\\$

则答案为 $\binom{n + 2}{n - 1} = \binom{n + 2}{3}$。

Sweet

显然，答案的生成函数为：

$\begin{aligned} \prod_{i = 1}^n \frac{1 - x^{m_i}}{1 - x} &= \frac1{(1 - x)^n}\prod_{i = 1}^n 1 - x^{m_i}\\ &= \sum_{i = 0}^\infty x^i \binom{n + i - 1}i \prod_{j = 1}^n 1 - x^{m_j}\\ &= \sum_{i = 0}^\infty x^i \binom{n + i - 1}i \sum_{j = 0}^\infty x^jc_j\\ &= \sum_{j = 0}^\infty x^jc_j \sum_{i = 0}^\infty x^i \binom{n + i - 1}i\\ \end{aligned}$

然后，$c_j$ 是可以直接 $O(2^n)$ 暴力展开求的，然后答案即为：

$\begin{aligned} \sum_{j = 0}^{b} c_j \sum_{i = a - j}^{b - j} \binom{n + i - 1}i = \sum_{j = a}^b c_j\left(\binom{n + b - j}n - \binom{n + a - j - 1}n\right) \end{aligned}$

可以 $O(2^n + b)$ 求。