生成函数学习笔记
lizhous
·
·
个人记录
概念
序列的母函数（生成函数）是一种形式幂级数。其每一项的系数可以提供关于这个序列的信息，使用母函数解决问题。
如：序列 a 的生成函数为 G(x)=\sum\limits_{i=1}^{n}a_if_i(x)。其中 f_i(x) 是无实际意义的，具体取值看题目要求。但有一些一般取值。
一般生成函数
令 f_k(x)=x^k，我们得到了一般形式的生成函数。
例题1：
有 n 种物品，第 i 种物品价值 v_i 有 num_i 个，问有多少种方案可以选若干物品价值和为 k。
使用一般生成函数解决。对每个物品构造母函数。第 i 个物品的母函数 G(i)=1+x_{v_i}+x_{2v_i}+\cdots +x_{num_iv_i}。x^k 表示这一种物品选了总价值为 k 的东西，用加法原理分离。相乘得到 \prod\limits_{i=1}^{n}G(i)。最终 x^k 的系数即为答案。
例题2：
有 n 种物品，第 i 种物品价值 v_i 有 num_i 个，问可以组合出多少种不同的价值。
使用一般生成函数解决。同上，最终项数即为答案。
蠢货板子
懒了。
特殊生成函数
叉义叉的博客就给出了一种：
对此类生成函数求导有：$G(x)=G'(x)
例：[国家集训队] 整数的lqp拆分
斐波那契生成函数 F(x)=\frac{x}{1-x-x^2}
设 n 的答案为 g_n，则 g_n=\sum g_{n-i}\times fib_i。
其中 g_0=1。
g$ 的生成函数为 $G(x)=\sum g_ix^i
则
G(x)=1+\sum (\sum g_j\times fib_{n-j})x^i\\
G(x)=1+\sum (g_j\times x^i)\times \sum fib_{n-j}\\
G(x)=1+G(x)\times \frac{x}{1-x-x^2}\\
G(x)=\frac{1}{1-\frac{x}{1-x-x^2}}\\
G(x)=\frac{1-x-x^2}{1-2x-x^2}=1+\frac{x}{1-2x-x^2}\\
展开 \frac{x}{1-2x-x^2}。
解出 1-2x-x^2 为 x_1,x_2。
套路的，写成两点式
G(x)=\frac{x}{-(x-x_1)(x-x_2)}
化成类似 \frac{1}{1-px} 的形式。
G(x)=-(\frac{1}{(x-x_1)}-\frac{1}{(x-x_2)})\times x\times\frac{1}{x_1-x_2}\\
G(x)=-(\frac{1}{(x_2-x)}-\frac{1}{(x_1-x)})\times x\times\frac{1}{x_1-x_2}\\
G(x)=-(\frac{1}{x_2}\times\frac{1}{(1-\frac{x}{x_2})}-\frac{1}{x_1}\times\frac{1}{(1-\frac{x}{x_1})})\times x\times\frac{1}{x_1-x_2}\\
G(x)=-(\frac{x}{x_2}\times\frac{1}{(1-\frac{1}{x_2}x)}-\frac{x}{x_1}\times\frac{1}{(1-\frac{1}{x_1}x)})\times\frac{1}{x_1-x_2}\\
G(x)=-(\frac{x}{x_2}\times\sum\frac{1}{x_2^i}x^i-\frac{x}{x_1}\times\sum\frac{1}{x_1^i}x^i)\times\frac{1}{x_1-x_2}\\
G(x)=-(\sum\frac{1}{x_2^{i+1}}x^{i+1}-\sum\frac{1}{x_1^{i+1}}x^{i+1})\times\frac{1}{x_1-x_2}\\
g(n)=(\frac{1}{x_2^{n}}-\frac{1}{x_1^{n}})\times\frac{1}{x_1-x_2}
带入 x=-1±\sqrt{2} 得
g(n)=(\frac{1}{(-1+\sqrt{2})^{n}}-\frac{1}{(-1-\sqrt{2})^{n}})\times\frac{1}{2\sqrt{2}}
calc即可。
记一些公式
A(x)=<a_0+a_1x+a_2x^2+\cdots>\\
B(x)=<b_0+b_1x+b_2x^2+\cdots>\\
C(x)=A(x)\times B(x)\\
c_n=\sum_{i=1}^{n} a_i\times b_{n-i}
等比数列求ogf\\
<1,p,p^2,p^3,\cdots>=\sum p^nx^n=\frac{1}{1-px}\\
(\frac{A(x)}{B(x)})'=\frac{A'(x)B(x)+A(x)B'(x)}{B^2(x)}
二项式 $n$ 项系数可以插板法求。
$$
\sum_{p=0}^{q} [x^p]\frac{1}{(1-x)^{m}}\\
=[x^q]\frac{1}{(1-x)^{m+1}}\\
=\binom{q+m}{m}
$$