我太弱了，指数型没看，求导也不是很熟练，所以推式子大部分都是套公式……
不过足矣。
我从四次元菊花里抽出来一个无限数列 \(a\)，我们定义它的生成函数 \(G(x) = \sum\limits_{i = 0}^{\infty} a_i x^i\)。
然后我们假装这个 \(x\) 是没有意义的，只是一个形式，并且叫这种式子形式幂级数。
但是它有什么用吗？
（可以拿来练习 FFT 和 NTT）
现在我们有一个方程 \(x_1 + x_2 + x_3 = 20\)，求它的非负整数解的个数。
显然可以插板法得到 \(\dbinom{22}{2}\)，但是我们假装不会插板法（
我们考虑把三个未知数的可能的解分别表示成数列 \(a_1,a_2,a_3\)。
具体地说，就是让 \(a_{1,i}\) 表示第一个未知数取值 \(i\) 的方案数，另两个类似。
即令 \(a_1 = a_2 = a_3 = \{1,1,\dots\}\)（因为除了要不大于 \(20\) 以外没有别的限制，并且这个限制我们也不用管）。
然后对三个序列构造生成函数 \(G_1(x) = G_2(x) = G_3(x) = \dfrac 1 {1 - x}\)（此处根据等比数列求和公式，并且 \(x \in (-1,1)\) 时 \(\lim\limits_{i \to \infty} x^i = 0\)）……
看到这里还是感觉没什么用啊……
然后呢，我们把三个生成函数乘起来，然后看一看 \(x^{20}\) 项的系数……
诶，这不就是答案？
其实多项式乘法的过程，就像是背包，分别枚举三个解，所以答案就出来了。
好的，然后我们来看一道用捆绑法 + 插板法就能解决的水题：（JZOJ 1337）
小 PP 超喜欢喝水，所以他就去买水了。
商店里有 \(5\) 种水：
1. 商店里有无数瓶；
2. 商店里只有一瓶；
3. 商店里竟然有 \(4\) 瓶；
4. \(5\) 瓶 \(5\) 瓶一包卖的；
5. \(2\) 瓶 \(2\) 瓶一包卖的。好奇心极强的小 PP 想买 \(n\) 瓶水，他想知道他有多少种买法。
\(n \le 2^{31} - 1\)。
转化一下，相当于求 \(x_1 + x_2 + x_3 + x_4 + x_5 = n\) 的非负整数解的个数，其中 \(0 \le x_2 \le 1,0 \le x_3 \le 4,5 | x_4,2 | x_5\)。
我们考虑对五个未知数分别构造生成函数，有 \[\begin{align*} G_1(x) & = \sum\limits_{i = 0}^{\infty} x^i = \dfrac 1 {1 - x} \\ G_2(x) & = \dfrac {1 - x^2} {1 - x} = 1 + x \\ G_3(x) & = \sum\limits_{i = 0}^4 x^i = \dfrac {1 - x^5} {1 - x} \\ G_4(x) & = \sum\limits_{i = 0}^{\infty} x^{5i} = \dfrac 1 {1 - x^5} \\ G_5(x) & = \sum\limits_{i = 0}^{\infty} x^{2i} = \dfrac 1 {1 - x^2} \end{align*}\]
相乘并因式分解得 \(\dfrac 1 {(1 - x)^3}\)。
得到这个有什么用呢？
我们可以考虑从生成函数反推回数列。
这个地方求导可以算但是太麻烦了，我们考虑换个思路。
发现这个就是 \((\sum\limits_{i = 0}^{\infty} x^{i})^3\)，考虑它的 \(x^n\) 项的系数。
根据插板法，其实就是 \(\dbinom{n + 2} 2\)！
然后记住一个重要的生成函数：\(\dfrac 1 {(1 - x)^n} = \sum\limits_{i = 0}^{\infty} \dbinom{n + i - 1}{n - 1} x^i\)，大部分普通型生成函数都能由它推出。
再举一个栗子：求自然数平方和，即 \(S(n) = \sum\limits_{i = 1}^n i^2\)。
考虑构造生成函数 \(G(x) = \sum\limits_{i = 0}^{\infty} S(i + 1) x^i\)。
那么显然有 \(G(x) - xG(x) = \sum\limits_{i = 0}^{\infty} (S(i + 1) - S(i)) x^i = \sum\limits_{i = 0}^{\infty} (i + 1)^2 x^i\)。
考虑后面这个生成函数等于什么。
观察发现 \((n + 1)^2 = \dbinom{n + 2}{2} + \dbinom{n + 1}{2}\)，所以根据之前那个式子，得到 \(G(x) = \dfrac{1 + x}{(1 - x)^4}\)。
于是第 \(n\) 项的系数为 \(\dbinom{n + 3}{3} + \dbinom{n + 2}{3}\)。
由于前面做了移位，所以 \(S(n) = \dbinom{n + 2}{3} + \dbinom{n + 1}{3}\)。
这个玩意也可以应用到其他常系数线性递推中去。