Steven_MengのBlog

这是一篇即将咕咕很久的学习笔记。

定义$f(x)=a_0+a_1x+a_2x^2+a_3x^3…$,$f(x)$就是序列$a_0,a_1,a_2…a_n$的生成函数

01背包问题

给你$w_1,w_2,w_3,…w_n$,每个数只有取和不取的两种状态,求凑成$W$的种类数。

构造$f(x)=\prod_{i=1}^n (x^0+x^{w_i})$,于是答案就是$x^W$的系数。

注意以下证明过程中$$省略。

完全背包问题

给你$w_1,w_2,w_3,…,w_n$,每个数可以取任意多种,求凑成$W$的种类数。

构造$f(x)=\prod_{i=1}^n (\sum _{j=0} x^{w_i\times j})$,答案就是$x^W$的系数。

$\sum _{j=0} x^{w_i \times j}$是无穷的,如何算出?

令$p=x^w_i$,那么有$\sum _{j=0} x^{w_i \times j}=\sum _{j=0} p^j$。

注意到$\sum _{j=0} p^j=\f\dfrac-p^\infty}{1-p}$,当$x \in (-1,1)$时,$p\in (-1,1)$,所以$p^ \to 0$,于是原式就是$\frac{1}{1\dfrac即$\frac{1}{1-\dfrac}$。

两种生成函数

前面介绍了第一种生成函数:$\sum _{j=0} ^{} x^j =\frac{1\dfrac}(x \in (-1,1))$

现在介绍第二种中的一个特殊情况:$\sum _{j=0}^{} (j+1) \times x^j=?$

我们把两个$\sum _{j=0} ^{} x^j$相乘,凑成$j$的有$(0,j),(1,j-1)…(j,0)$这么多种,共$j+1$种选法。

于是$\sum _{j=0} (j+1) \times x^j=\dfrac1}{(x-1)^2}$

推广一下:

$\dfrac{1}{(x-1)^k}$是什么?

问题转化为凑出$k$个数,使他们的和为$j$的方案数。

插板法即可,答案为$C_{j+k-1}^{k-1}$

于是$\dfrac1}{(x-1)^k}=\sum_{j=0} C_{j+k-1}^{k-1} x^j$

注意到$C_{j+k-1}^{k-1}=C_{j+k-1}^j$,这个形式在下面的广义二项式定理里面会用到。

于是我们总结出以下规律:

$\dfrac{1}{1-x^k}=\sum _{j=0} x^{jk}$

$\dfrac{1}{(1-x)^k}=\sum_{j=0} C_{j+k-1}^{k-1} x^j$

还有一个有限项数的求和公式:

$\dfrac{1-x^{k+1}}{1-x}=\sum _{j=0}^k x^k$

广义二项式定理

注意到$\f\dfrac}{(1-x)^k}=(1-x)^{-k}$。

我们不禁有个大胆的想法,如果$k$可以取任何实数,那么我们就可以表示出$\sqrt{1-x},\sqrt[3]{1-x}$等等的生成函数。

$(1+x)^\alpha = \sum_{j=0} C_{j}^{\alpha} x^j$。

定义:

$C_{\alpha}^{k}=\begin{cases} \dfrac{\alpha(\alpha-1)(\alpha-2) \dots (\alpha-k+1)}{k!},k>1 \ 1,k=0 \ 0,k<0 \end{cases}(k \in \mathbb{Z},\alpha \in \mathbb{R}) \tag{1.1.1}$

来自巨佬ypy的博客

生成函数的应用

例题1

BZOJ 3028

承德汉堡:$f(x)=1+x^2+x^4+x^6…=\fr\dfrac{1-x^2}$

可乐:$f(x)=1+x$

鸡腿:$f(x)=1+x+x^2=\f\dfrac-x^3}{1-x}$

蜜桃多:$f(x)=\sum_{j=0} x^j - (1+x^2+x^4+…)=\f\dfrac}{1-x}-\f\dfrac}{1-x^2}=\f\dfrac}{1-x^2}$

鸡块:$f(x)=\f\dfrac}{1-x^4}$

包子:$f(x)=1+x+x^2+x^3=\f\dfrac-x^4}{1-x}$

土豆片炒肉:$f(x)=1+x$

面包:$f(x)=\f\dfrac}{1-x^3}$

乘起来然后大力化简一波,化成了$\frac{x}{\dfrac^4}$

套进第二个式子:

$\dfrac{x}{(1-x)^4}=\sum_{j=0} C_{j+3}^{3}x_{j+1}=\sum_{j=1} C_{j+2}^{3}x_{j}$

于是我们所求的就是$C_{j+2}^3$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define MAXN 200005
#define MOD 10007
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=((x<<3)+(x<<1)+(ch^'0'))%MOD;
ch=getchar();
}
return x*f;
}
inline int ksm(int b,int k){
int ans=1;
while (k){
if (k&1) ans=(ans*b)%MOD;
b=(b*b)%MOD;
k>>=1;
}
return ans;
}
int main(){
int n=read();
printf("%d\n",(n+2)*(n+1)%MOD*(n)%MOD*ksm(6,MOD-2)%MOD);
}

例题2

P2000 拯救世界

本质和上面一题是一样的:

kkksc03:

金:$\dfrac1}{1-x^6}$

木:$\dfrac1-x^{10}}{1-x}$

水:$\dfrac1-x^6}{1-x}$

火:$\dfrac1}{1-x^4}$

土:$\dfrac1-x^8}{1-x}$

lzn:

金:$\dfrac1}{1-x^2}$

木:$1+x$

水:$\dfrac1}{1-x^8}$

火:$\dfrac1}{1-x^{10}}$

土:$\dfrac1-x^4}{1-x}$
大力乘起来,算出$\fra\dfrac1-x^5}$

答案即是$C_{n+5-1}^{5-1}=C_{n+4}^4$。

只写了python版本:

1
2
n=(int)(input())
print((n+1)*(n+2)*(n+3)*(n+4)//24)

例题3

试用生成函数推导斐波那契数列通项公式。

斐波那契数列:$fib_1=1,fib_2=1,fib_i=fib_{i-1}+fib_{i-2} (i\ge 3)$

构造$f(x)=\sum _{j=1} fib_j x^j$

所以$f(x) \times x=\sum_{j=2} fib_{j-1}x^j$

$f(x)-f(x)\times x=fib_1x+\sum_{j=3}^{}fib_{j-2}x^j=x+x^2\times f(x)$

所以$f(x)=\f\dfrac}{1-x-x^2}$

令$\phi =\dfrac1+\sqrt{5}}{2},\phi’=\dfrac1-\sqrt{5}}{2}$。

分解:$\f\dfrac}{1-x-x^2}=\f\dfrac}{(1-\phi’x)(1-\phi x)}=\f\dfrac}{\sqrt{5}}(\f\dfrac}{1-\phi x} - \f\dfrac}{1-\phi’ x})$

根据公式$\f\dfrac}{1-x}=\sum _{j=0} x^{j}$,前面一项化为$(\phi)^n$后面一项化成$(\phi’)^n$。

于是我们得到$fib_n=\fr\dfrac{\sqrt{5}}(\phi ^n-\phi’^n)$。

即$fib_n=-\dfrac1}{\sqrt 5}(\dfrac1-\sqrt 5}{2})^n+\dfrac1}{\sqrt 5}(\dfrac1+\sqrt 5}{2})^n$。

补充

已知$f_0=A,f_1=B,f_i=pf_{i-1}+qf_{i-2} (i \ge 2)$

构造$f(x)=\sum _{j=1} f_j x^j$

所以$f(x) \times x= \sum _{j=2} f_{j-1} x^j$

得到$f(x)-pf(x) \times x=Cx + \sum _{j=2} f_{j-2}x^j=Cx+q x^2 f(x)$(其中$C$是一个常数,我们可以不用管它,原理在你使用时自然清楚)

得到$f(x)-px f(x) -qx^2 f(x)=Cx$,于是有$f(x)=\fr\dfrac}{1-px-qx^2}$。

设方程$x^2-px-q=0$的解是$x_1,x_2$($x_1,x_2$又称特征根),注意到把$x=\frac{1}{x_\dfrac$1-px-qx^2$,变成$1-\frac{p}{x_1}-\dfrac{q}{x_1^2\dfracac{x_1^2-px\dfrac{x_1^2}$

显然为$0$。

于是可以转化为$f_n=C_1 x_1 ^n +C_2x_2^n$

你肯定有疑问,为什么不算出来$C_1,C_2$,直接无脑带进去就好。

事实上$C_1,C_2$公式非常复杂,你肯定也记不住。

考试时,可以解出$C_1,C_2$。

比如一道题:$h_0=1,h_1=3,h_n=2h_{n-1}+2h_{n-2} (n\ge 2)$。

特征根:$x^2-2x-2=0 \to x_{1,2}=\f\dfrac \pm \sqrt {4+8}}{2}={1\pm \sqrt{3}}$

带入$h_0=C_1 +C_2,h_1=C_1x_1+C_2x_2$(这里我们特意算出来$h_0$以简化计算)

得到$C_1+C_2=1,C_1(1+\sqrt {3}) +C_2(1-\sqrt{3})=3$

解得$C_1=\dfrac2 \sqrt {3}+3}{6},C_2=\dfrac-2 \sqrt {3}+3}{6}$

通项公式$h_n=\f\dfrac \sqrt {3}+3}{6} (1+\sqrt{3})^n + \f\dfrac2 \sqrt {3}+3}{6} (1-\sqrt{3})^n$

例题4

试用生成函数推导卡特兰数通项公式。

卡特兰数:

$c’_0=1$

$c’_1=1$

$c’_n=\sum_{i=1}^{n-1}c’_ic’_{n-i-1}$

为了方便,记$c_i=c’_{i-1}$,有$c’_i=c_{i+1}$。

所以有$c_n=c’_{n-1}=\sum_{i=1}^{n-2}c’_ic’_{n-i-2}=\sum_{i=1}^{n-2}c_{i+1}c_{n-i-1}=\sum_{i=2}^{n-1}c_ic_{n-i} $

记$C(x)=\sum _{i=0} c_ix^i$

有$C(x)-C(x)^2=C_1 \times x^1=x$。

于是$C(x)^2-C(x)+x=0$

得到$C(x)=\dfrac1\pm\sqrt{1-4x}}{2}$

舍去$\dfrac1+\sqrt{1-4x}}{2}$

所以$C(x)=\f\dfrac}{2x}[1-(1-4x)^{0.5}]$

先化简$(1-4x)^{0.5}$

由$(1+x)^\alpha = \sum_{j=0} C_{j}^{\alpha} x^j$

有$(1-4x)^{0.5}=\sum_{j=0} C_{0.5}^{j}(-4x)^j$。

注意到这里$C_{0.5}^0(-4x)^0=1$,把它放到前面去。

拆一波$C_{0.5}^{j}=\f\dfracprod_{k=0}^{j-1} (0.5-k)}{j!}$

放回去:$\sum_{j=1}^ \f\dfracprod_{k=0}^{j-1}(0.5-k)}{j!} \times (-4x)^j$

右边除掉一个$(-2)^j$,左边乘$(-2)^j$

变成:$\sum_{j=1}^ \f\dfracprod_{k=0}^{j-1}(2k-1)}{j!} \times (2x)^j$

注意到$\sum_{k=0}^{j-1}=-1\times (1 \times 3 \times 5 \times … \times (2j-3))$,这里我们把那个$-1$放到前面抵消掉减号,下面不再说明。

这时可以发现$(1 \times 3 \times 5 \times … \times (2j-3))= \fr\dfracj-2)!}{2^{j-1}(j-1)!}$

于是我们可以得到$(1-4x)^{0.5}=1-\sum_{j=1} 2^j x^j \times \fra\dfrac-2)!}{2^{j-1}(j-1)!} \times \fra\dfracj!}$

等于$1-\sum_{j=1} x^j \times 2\dfrac(2j-2)!}{(j-1)!j!}$

带回原式$C(x)=\f\dfrac}{2x}[1-(1-\sum_{j=0} x^j \times 2\f\dfrac2j-2)!}{(j-1)!j!})]$

等于$\sum_{j=1} x^{j-1} \times \dfrac(2j-2)!}{(j-1)!j!}$。

注意到$x$的次数不能是$j-1$,于是把$k=j-1$带入,变成$\sum _{k=0} x^k \times \frac{(2k)\dfrac(k+1)!}$

于是得到公式$c_n=\fr\dfracn)!}{n!(n+1)!}$

 评论