生成函数（LHT称之为母函数），是一种有趣的工具，目前只知道可以优美地处理组合问题。
设存在一个数列Ai，其普通生成函数的定义：
\[F(X) = \sum_{i=0} t_iX^i\]其中ti为数列的第i项
这个东西有什么用？就是用一个函数表示数列？举个例子：有两类物品，A类物品无限个，可以随便选；B类物品无限个，但只能选偶数个；用数列Ai,Bi表示
该类物品选i个的方案数；显然，Ai={1,1,1,1......},Bi={1,0,1,0,1,0........},用函数表示：\(A(X)=1+x+x^2+x^3+......\),\(B(x)=1+x^2+x^4+......\)
我们发现，F(x) = A(x)*B(X)为数列的卷积，F(x)中 \(x^i\)的系数为两物品一共选i个的方案数。但直到现在，我们还是没有办法有效利用她。
对A(x)进行变换：根据等比数列求和公式，在\(x\epsilon (-1,1)\)时，A(x) = \(\frac{1-x^n}{1-x} = \frac{1}{1-x}\) ;令\(x=x^2,可以得到B(x)=\frac{1}{1-x^2}\)
同样，\(\frac{1}{(1-x)^k} = \sum_i=0 \binom{i+k-1}{k-1}*x^i\)，利用了高中的隔板法：即 K个非负整数相加,和为i的方案数。
同样 \(\frac{1}{1-ax} = \sum_i=0 a^i*x^i\)，这个十分显然。
知道了这些，在有些组合问题中，我们可以令其母函数相乘，得到一个函数，再将其转化为数列QwQ
$f_n = {1,1,2,3,5,8......},令g(x) = \sum_i=1 f_i*x^i ,得到g(x) =
原文：https://www.cnblogs.com/bullshit/p/12276084.html