生成函数-学习笔记

### 整数划分 将n分解为若干正整数的和，可以重复选。 $(1+x+x^2+x^3...)(1+x^2+x^4...)...$ 然后第n项的系数就是答案。 ### BZOJ 3028 食物 $\begin{align} 汉堡 & = x^0 + x^2 + x^4 + \cdots = \frac{1}{1-x^2} \\ 蜜桃 & = x^1 + x^3 + x^5 + \cdots = \frac{x}{1-x^2} \\ 面包 & = x^0 + x^3 + x^6 + \cdots = \frac{1}{1-x^3} \\ 鸡块 & = x^0 + x^4 + x^8 + \cdots = \frac{1}{1-x^4} \\ 土豆 & = x^0 + x^1 = \frac{1-x^2}{1-x} \\ 可乐 & = x^0 + x^1 = \frac{1-x^2}{1-x} \\ 鸡腿 & = x^0 + x^1 + x^2 = \frac{1-x^3}{1-x} \\ 包子 & = x^0 + x^1 + x^2 + x^3 = \frac{1-x^4}{1-x} \\ \end{align}$ 乘起来就是$f(x) = \frac{x}{(1-x)^4}$ 然后联系到$\frac{1}{1-x}$的实际含义（或者直接套公式而$\left( \sum_{i=0}^{\infty} x^i \right)^n$中的x的a次项的系数是$\binom{a+n-1}{n-1}$） 因为前边乘了一个x，所以我们求的是n-1项：$C^3_{n+2}$ ------------ ## 指数生成函数   ~~不会~~