生成函数学习笔记

挖坑不填

等有空了大概会填的吧

生成函数定义

$G(x) = g_0+g_1x+g_2x^2+…… = \sum_{n>=0} g_nx^n$,我们称$G$或者$G(z)$是数列$<g_0,g_1,…>$的生成函数。

常用生成函数

$$
\sum_{n>=0}[n=0]z^n = 1\
\sum_{n>=0}z^n = \frac{1}{1-z}\\sum_{n>=0}(-1)^nz^n = \frac{1}{1+z}\\sum_{n>=0}\binom{m}{i}z^n = (1+z)^m\\sum_{n>=0}\binom{n+m-1}{n}z^n = \frac{1}{(1-z)^m}\\sum_{n>=1}\frac{1}{n}z^n = \ln\frac{1}{1-z}\\sum_{n>=1}\frac{(-1)^{n+1}}{n}z^n = \ln(1+z)\\sum_{n>=0}\frac{1}{n!}z^n = e^x
$$

写到这里发现自己不会$\ln$这玩意儿

感觉自己多项式也一窍不通……发现自己$ln$是啥都不知道

$exp$是怎么定义来着的?$exp(A(x)) = \sum_{i>=0}\frac{A^i(x)}{i!}$

$ln$只知道一个结论:$ln(x) = \frac{1}{x}$,所以$ln(f(x)) = \int\frac{f’(x)}{f(x)}$?大概就是对的吧

把$f(x) = e^{g(x)}$代进去,发现$ln(e^{g(x)}) = \int\frac{e^g(x)*g’(x)}{e^{g(x)}} = g(x)$

看起来非常真。嗯。

生成函数运算

是生成函数的一些运算,大概就是多项式的一些运算。

有一个就是求前缀和就是卷积上$<1 ,1,1,1,…> = \frac{1}{1-z}$

简单生成函数求法

举一个例子吧,比如说斐波那切数列的生成函数,因为有$f(x)=f(x-1)+f(x-2)$有$F = xF + x^2F + 1$,所以是$F = \frac{1}{1-x-x^2}$

解递归式

大概就是知道生成函数求通项公式,看起来在做数列题的时候可能会有点用?

一类特殊的生成函数

大概是分母可以进行部分分式分解的

一个需要证明的东西:

$R(z) = \frac{P(z)}{Q(z)}$,其中$P$,$Q$是多项式,然后要求R的第n项的系数。

根据刚才的东西,我们知道
$$
\frac{1}{(1-px)^{m+1}} = \sum_{n>=0}\binom{m+n}{m}p^nz^n
$$
这东西可以快速算它的一个位置上的值。

然后如果是若干个上面的东西的和
$$
\frac{a_1}{(1-p_1x)^{m_1}} + \frac{a_2}{(1-p_2x)^{m_2}}+…
$$
也是很好求的,只需要把每一项的系数加起来就行了。

然后可以证明对于$R(0) \not= \infty$的有理函数$R(x)$都可以表示成$R(x) = S(x) + T(x)$,其中S是上面那个形式,T是一个多项式。【不知道为什么,不会证明】

所以主要是要部分分式分解。

先考虑如何把下面的那些$p_i$求出来。

假如$Q(x) = q_0+q_1x+…+q_mx^m | q_0\not=0,q_m\not=0$

我们令$Q^R(x) = q_0x^m+…+q_m$

有$Q^R(x) = q0(x-\rho_0)(x-\rho_1)…(x-\rho_m)$

有$Q(x) = q0(1-\rho_0x)(1-\rho_1x)…(1-\rho_mx)$

也就是$Q^R$的根是$Q$的根的倒数。

也就是,我们对$Q^R$进行求根,就能得到这若干个$\rho$的值,先假设这些$\rho$都不相同(有相同不会)

然后是主要分解部分

大概就是如果一个函数本来是
$$
\frac{P(x)}{Q(x)}=\frac{P(x)}{(1-\rho_1x)(1-\rho_2x)(1-\rho_3x)…}
$$
那么可以把它分解成
$$
\frac{a_1}{1-\rho_1x} + \frac{a_2}{1-\rho_2x} ……
$$
其中$a_1,a_2$这些都是常数,这个东西就是可以直接算结论的了。

嗯,感觉手解递推式的话上面手动分解,下面手动待定系数来求就行了。

那如何用计算机来做这个部分分式分解呢?(还是要$\rho$不同的情况)

$a_i$就是$a_i = \Large \frac{P(\frac{1}{\rho_i})}{Q_i(\frac{1}{\rho_i})}$

$Q_i(x) = Q(x) / (1-\rho_ix)$

这东西证明大概就是,把这n个点代进去,发现和原来的式子的答案都是一样的。

具体就是,通分之后,只有一个乘积的式子是有值的,剩下的都是0,然后又值的那个式子和原式子是一样的。

然后怎么快速计算$Q_i(\frac{1}{\rho_i})$

这东西就直接对Q求导,然后直接把$\frac{1}{\rho_i}$代到$Q’$里面就行了。

这东西用多项式多点求值可以在两个log的复杂度里面做出来。

文章目录
  1. 1. 生成函数定义
  2. 2. 常用生成函数
  3. 3. 生成函数运算
  4. 4. 简单生成函数求法
  5. 5. 解递归式
    1. 5.1. 一类特殊的生成函数
  6. 6.