生成函数1
生成函数（generating function），又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。
其用来计算组合数中诸如选择某一数量方案数的一种强有力的工具
加法生成函数
也算常生成函数啦
对于一个生成函数，将其定义为形式幂级数
如：
F ( x ) = ∑ n a n x n F(x) = \sum_na_nx^n F(x)=n∑anxn
其中a可以是有穷数列，也可以是一个无穷数列
我们通常这么写
a = < 1 , 2 , 3 > → 1 + 2 x + 3 x 2 a = < 1 , 1 , 1 , 1 , 1 > → 1 + x + x 2 + x 3 + x 4 a = < 1 , 1 , 1.... > → ∑ n ≥ 0 x n a=<1,2,3>\rightarrow 1+2x+3x^2\\ a=<1,1,1,1,1>\rightarrow 1+x+x^2+x^3+x^4 \\ a=<1,1,1....>\rightarrow \sum_{n\ge 0}x^n a=<1,2,3>→1+2x+3x2a=<1,1,1,1,1>→1+x+x2+x3+x4a=<1,1,1....>→n≥0∑xn
后面的形式就是其生成函数
其实也就是： ( 1 + x ) n (1+x)^n (1+x)n，展开利用二项式定理啊，即 1 + C n 1 x + C n 2 x 2 + ⋯ + c n n x n 1+C_n^1x+C_n^2x^2+ \dots + c_n^n x^n 1+Cn1x+Cn2x2+⋯+cnnxn
比如我们在这一堆中选k个，那么方案数就是 x k x^k xk的系数
是不是非常神奇！！！
那么我们现在考虑如下一个问题
两种物体a,b都有无限个，求取出n个的方案数
发现这个东西有两个数列，那么我们就可以根据这两个数列分别构造他们的母函数: A n , B n A_n,B_n An,Bn
怎么把他们搓在一起，解决一共选n个的问题
这个东西就叫做：生成函数卷积
就是 H n = A 0 B n + A 1 B n − 1 . . . A n B 0 H_n=A_0B_n+A_1B_{n-1}...A_nB_0 Hn=A0Bn+A1Bn−1...AnB0
下面我们来讨论一下母函数的性质吧
- 放缩 < c g 0 , c g 1 , c g 2 , , . . . > ⇒ c G ( x ) = c g 0 , c g 1 , . . . <cg_0,cg_1,cg_2,,...>\Rightarrow cG(x)=cg_0,cg_1,... <cg0,cg1,cg2,,...>⇒cG(x)=cg0,cg1,...
- 加减 < f 0 ± g 0 , f 1 ± g 1 , . . . > ⇒ F ( x ) ± G ( x ) = f 0 ± g 0 + f 1 ± g 1 . . . . <f_0\pm g_0,f_1 \pm g_1 ,...>\Rightarrow F(x)\pm G(x) = f_0\pm g_0+f_1 \pm g_1 .... <f0±g0,f1±g1,...>⇒F(x)±G(x)=f0±g0+f1±g1....
- 右移 < 0 , 0 , . . . 0 , g 0 , g 1 , . . . > <0,0,...0,g_0,g_1,...> <0,0,...0,g0,g1,...>，前面k个0， ⇒ x k G ( x ) \Rightarrow x^kG(x) ⇒xkG(x)
- 求导 G ′ ( x ) = g 1 + 2 g 2 x + 3 g 3 x 2 . . . ⇒ < g 1 , 2 g 2 , 3 g 3 , . . > G'(x) = g_1+2g_2x+3g_3x^2... \Rightarrow <g_1,2g_2,3g_3,..> G′(x)=g1+2g2x+3g3x2...⇒<g1,2g2,3g3,..>其实就是n-1的方案数
这些性质都非常重要且常用不过这玩意本来也不怎么考就对了