一般生成函数

bzoj3028: 食物

裸题。
可乐的贡献:$1+x$
汉堡的贡献:$1+x^2+x^4+x^6…=\frac{x^{+\infty}-1}{x^2-1}$
鸡腿的贡献:$1+x+x^2=\frac{x^3-1}{x-1}$
蜜桃多的贡献:$x+x^3+x^5…=\frac{x^{+\infty}-x}{x^2-1}$
鸡块的贡献:$1+x^4+x^8+x^{12}…=\frac{x^{+\infty}-1}{x^4-1}$
包子的贡献:$1+x+x^2+x^3=\frac{x^4-1}{x-1}$
土豆片炒肉的贡献:$1+x$
面包的贡献:$1+x^3+x^6+x^9…=\frac{x^{+\infty}-1}{x^3-1}$
将他们乘到一起!
$f(x)=(1+x)\cdot\frac{x^{+\infty}-1}{x^2-1}\cdot\frac{x^3-1}{x-1}\cdot\frac{x^{+\infty}-x}{x^2-1}\cdot\frac{x^{+\infty}-1}{x^4-1}\cdot\frac{x^4-1}{x-1}\cdot(1+x)\cdot\frac{x^{+\infty}-1}{x^3-1}$
loli给我说一般认为|x|<1,否则级数不收敛。这样的话
$f(x)=\frac{x}{(x-1)^4}$
我们可以用广义二项式定理,即求$(x-1)^{-4}$的n项的系数,即$\binom {-4}{n}(-x)^n=\frac{(n+3)(n+2)(n+1)}{6}$
也可以
$g(x)=\frac{1}{(x-1)^4}=(1+x+x^2+x^3…)^4$,第n项的系数相当于将n个相同的球放入4个不同的盒子,每个盒子可以为空,求方案数,这就是$C_{n+3}^{3}$

bzoj3027: [Ceoi2004]Sweet

最后的生成函数:
$\prod\limits_i^n(1+x+x^2+…+x^{m_i})=\prod\limits_i^n {1-x^{m_i+1}\over 1-x} \\= {\prod\limits_i^n (1-x^{m_i+1})\over (1-x)^n}=(1+x+x^2+x^3…)^n\prod\limits_i^n (1-x^{m_i+1})$
后面那一部分最多产生2^n个系数不为0的项,所以我们可以直接爆搜,然后前面部分我们可以直接组合数求得:如果我们要求前面的第0项到第p项系数的和,那么公式为$C_{p+n}^{n}$。就完了
然后这道题处理时有一个技巧,因为他的P不为质数,所以可能不存在逆元,我们求组合数的时候直接暴力算,然后求出n!,然后求组合数的时候模(n!*P),最后再除以(n!)就行了。

bzoj3992: [SDOI2015]序列统计

这道题我们可以通过找原根的方式将乘法变成在指数上的加法,然后就是很裸的生成函数了.

bzoj3771: Triple

题意:n个物品,可以用1/2/3个不同的物品组成不同的价值,求每种价值有多少种方案(顺序不同算一种)
设$B_{t}=x^{tw_{1}}+x^{tw_{2}}+x^{tw_{3}}+x^{tw_{4}}…x^{tw_{n}}$
只拿三个物品的生成函数为$\frac{B_{1}^3+2B_{3}-3B_{2}B_{1}}{6}$
只拿两个物品的生成函数为$\frac{B_{1}^2-B_{2}}{2}$
只拿一个物品的生成函数为$B_{1}$
加在一起得$B_{1}+\frac{B_{1}^2-B_{2}}{2}+\frac{B_{1}^3+2B_{3}}{3}-B_{2}B_{1}$

bzoj4001

先搞一下卡特兰数的生成函数推导:
$$H_{i}=\sum_{j=0}^{i-1}H_{j}\cdot H_{i-1-j}$$
设卡特兰数的生成函数为$C(z)$
$$C(z) = \frac{1 \pm \sqrt{1 - 4z}}{2z}$$
为了收敛
$$C(z) = \frac{1 - \sqrt{1 - 4z}}{2z}$$
根据广义二项式定理展开
$\sqrt{1-4z} = \left (1-4z \right )^{\frac{1}{2}} = \sum_{i=0}^{\infty}\binom{\frac{1}{2}}{i}(-4z)^i$
考虑第n项的系数,
那就是
$$\begin{eqnarray}
& &(-4)^n \binom{\frac{1}{2}}{ n }\\
&=& (-4)^n \frac{\frac{1}{2}\cdot \left( \frac{1}{2} -1 \right)\cdot \left( \frac{1}{2} -2 \right)\cdots \left( \frac{1}{2} - n + 1 \right)}{1\cdot2\cdot3\cdots n}\\
&=& (-2)^n \frac{1\cdot (1-2)\cdot (1-4)\cdots (1 - 2n + 2)}{1\cdot2\cdot3\cdots n}\\
&=& -\frac{1\cdot 3\cdot 5\cdots (2n - 3)}{1\cdot2\cdot3\cdots n}\cdot \frac{1\cdot 2\cdot 4\cdots 2n}{1\cdot 2 \cdot 3 \cdots n}\\
&=& -\frac{(2n)!}{(2n-1)(n!)^2}\\
&=& -\frac{1}{2n-1}\binom{2n}{n}
\end{eqnarray}$$
因此可以得到
$$\begin{eqnarray}
C(z) &=& \frac{1-\sqrt{1-4z}}{2z}\\
&=&\frac{1+\sum_{i=0}^{\infty}\frac{1}{2i-1}\binom{2i}{i} z^i}{2z}\\
&=&\frac{\sum_{i=1}^{\infty}\frac{1}{2i-1}\binom{2i}{i} z^{i-1}}{2}\\
&=&\sum_{i=0}^{\infty}\frac{2}{2i+1}\binom{2i+2}{i+1} z^i\\
&=&\sum_{i=0}^{\infty}\frac{1}{2}\cdot\frac{1}{2i+1}\cdot\frac{(2i+1)(2i+2)}{(i+1)^2}\binom{2i}{i} z^i\\
&=&\sum_{i=0}^{\infty}\frac{1}{n+1}\binom{2i}{i} z^i\\
\end{eqnarray}$$
然后得到$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

设$f_{i}$表示所有大小为i的二叉树的叶子节点总和

那么转移为$f_n = 2\sum_{i=0}^{n-1} f_i \cdot H_{n-i-1}$
设f的生成函数为$F(x)$那么:
$$\begin{eqnarray} F(x) &=& 2xF(x)H(x)+x \end{eqnarray}$$
解得$$\begin{eqnarray} F(x) &=& \frac{x}{\sqrt{1-4x}} \end{eqnarray}$$
考虑$(1-4x)^{-\frac{1}{2}}$的第n项,
$$\begin{eqnarray}
& &(-4)^n \binom{-\frac{1}{2}} {n }\\
&=& (-4)^n \frac{-\frac{1}{2}\cdot \left( -\frac{1}{2} -1 \right)\cdot \left( -\frac{1}{2} -2 \right)\cdots \left( -\frac{1}{2} - n + 1 \right)}{1\cdot2\cdot3\cdots n}\\
&=& (-2)^n \frac{-1\cdot (-1-2)\cdot (-1-4)\cdots (-1 - 2n + 2)}{1\cdot2\cdot3\cdots n}\\
&=& \frac{1\cdot 3\cdot 5\cdots (2n - 1)}{1\cdot2\cdot3\cdots n}\cdot \frac{1\cdot 2\cdot 4\cdots 2n}{1\cdot 2 \cdot 3 \cdots n}\\
&=& \frac{(2n)!}{(n!)^2}\\
&=& \binom{2n}{n}
\end{eqnarray}$$
$x(1-4x)^{-\frac{1}{2}}$的第n项系数即$F_{n}$为$\binom{2n-2}{n-1}$
所以$\frac{F_{n}}{H_{n}}=\frac{n^2+n}{4n-2}$


指数生成函数

数列$h_{0},h_{1},h_{2},…,h_{n},…$的指数生成函数定义为

$$g^{(e)}(x)=\sum_{n=0}^{\infty}h_{n}\frac{x^n}{n!}=h_{0}+h_{1}x+h_{2}\frac{x^2}{2!}+…+h_{n}\frac{x^n}{n!}…$$

$$e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}=1+x+\frac{x^2}{2!}+…+\frac{x^n}{n!}…$$

更一般地
$$e^{ax}=\sum_{n=0}^{\infty}a^n\frac{x^n}{n!}=\sum_{n=0}^{\infty}\frac{(ax)^n}{n!}$$