「OI之路」03数学-13生成函数

生成函数

可能需要一些基本微积分知识

本文没有严谨这种东西,如果你发现有某些定义上感觉无法理解(如e、积分的法则),强烈推荐rqy
当然会有一些可以看的课件,例如策的

和生成函数沾边的东西,默认A表示函数,a表示其系数(指大小写)

概念

幂级数:形如 $\sum_{i=0}^{\infty} a_i(x-x0)^i$

形式幂级数:不讨论幂级数敛散性,也就是将其中的不定元x仅仅看作是一个代数对象,而不是任何具体数值的时候写出的幂级数。生成函数就是一种形式幂级数

所以这就是生成函数的精髓所在:用一个无限多项式的形式,却不需要考虑是否有意义,可以便捷地对数列做类似多项式的各种运算,最后再展开回去(如e^x就是一个数列)

下面会有些习题,懒得搞折叠了,可以学之前截个图打马赛克

一些符号(其实都是常识):$(f \circ g)(x) = f(g(x)),\frac{\mathrm d f(x)}{\mathrm dx} = f’(x),\int f’(x) \mathrm dx = f(x) + C$

一般生成函数OGF

$$
序列a的OGF:f(x)=\sum_{i=0}^{\infty} a_ix^i \\
应当熟记的常见OGF: \\
(1+x)^n=\sum C_n^i x^i,
\frac{1}{(1-x)^m}=\sum C_{n+m-1}^{m-1} x^n,理解考虑将n隔板成m个可空组
\\
F’(x)=\sum_n(n+1)f_{n+1}x^n,\int_0^xF(t)\mathrm{d}t=\sum_{n=1}\frac{f_{n-1}}nx^n\\
$$

序列左右移,可以通过乘除x来实现


一些练习:

  1. 证明、辅助记忆范德蒙德等式(提示:$(1+x)^{m+n}=(1+x)^m(1+x)^n$,虽然组合意义考虑是显然,练练手吧)

  2. 化简生成函数$\sum i^2x^i$ :$(1-x)f(x)=\sum_{i=1}(2i-1)x^i,f(x)=\frac{x(x+1)}{(1-x)^3}$

  3. 求卡特兰数的生成函数:$卡特兰数卷积形式递推,F为f的生成函数,可化出 F(x)=1+xF^2(x),求根公式\\然后考虑一下F(0)=1和洛必达法则可得 F(x)=\frac{1-\sqrt{1-4x}}{2x},可广义二项式展开验证$

  4. 「TJOI2015」概率论

$$
设g(x)为x个节点的所有二叉树叶子节点之和,G为其生成函数,F为上面刚推完的卡特兰数\\
还是考虑二叉树递推,可得 G(x)=2xG(x)F(x)+x\\
G(x)=\frac{x}{\sqrt{1-4x}},展开得g(x)恰好=Cat(x-1)
$$

  1. 「国家集训队」整数的lqp拆分

    设G为g的生成函数,$G=G*Fib+Fib->G=\frac{x}{1-2x-x^2}$

  2. bzoj3625 、CF438E The Child and Binary Tree

    $F=cF^2+1,牛顿迭代的话就做完了,也可以考虑洛必达法则化式子:F=\frac{1-\sqrt{1-4C}}{2C}$

    虽然C没有逆元,但可以考虑怎么消掉: $F=\frac{1-(1-4C)}{2C(1+\sqrt{1-4C})}=\frac{2}{1+\sqrt{1-4C}}$

指数生成函数EGF

众所周知,长度n的序列,k种颜色随便涂的方案数=$\frac{n!}{\prod times_{col}!}$

然后生成函数一次考虑一种颜色的话,考虑把下面的$i!$丢到$x^i$下面作为分母
$$
序列a的EGF: f(x)=\sum_{i=0}^n a_i \frac{x^i}{i!}
\\
\sum_{i=0}^{\infty} a^i\frac{x^i}{i!}=e^{ax},
\sum_{i=0}(-1)^i\frac{x^{2i+1}}{(2i+1)!}=sin(x),\sum_{i=0}(-1)^i\frac{x^{2i}}{(2i)!}=cos(x)
\\
ln(\frac{1}{1-x})=-ln(1-x)=\sum_{i=1} (i-1)! \frac{x^i}{i!},化式子可能用到\frac{-a}{1-ax}=[ln(1-ax)]’ \\
x^ke^x=\sum_{i=k}^{\infty} i^{\underline k} \frac{x^i}{i!}
$$
上面ln的第一个公式证明:两边exp,右边其实是轮换(环),卷成置换(排列)后就是排列数的EGF($\frac{1}{1-x}$),故这个式子请记住其组合意义

序列的左右移,可以用求积分、求导实现(发现没,超方便)

还有就是这东西显然和OGF是不同的,例如排列数的EGF=数列1,1,1……的OGF

但真正熟练的时候,是不需要强调啥的,会用就行


一些练习:

  1. 证明、辅助记忆二项式反演的正三角形式(提示:$F=G*e^x$)

  2. CF891E Lustcode
    $$
    \begin{aligned}
    考虑&题意转化,发现每次乘积减少多少res就增加多少\\
    res&=\prod a_i-E(\prod (a_i-times_i)) \\
    后面&=\frac{k!}{n^k} \prod_i[ \sum_j (a_i-j)\frac{x^j}{j!} ] [x^k]\\
    &=[\frac{k!}{n^k}e^{nx} * \prod_i(a_i-x)][x^k] \\
    & =\sum_{i=0}^{min(n,k)} [\prod_t(a_t-x)][x^i]*\frac{k!}{n^i(k-i)!}
    \end{aligned}
    $$

  3. CF623E Transforming Sequence,bzoj5381 or

    收获:传进去的自变量要灵活运用(事实上讲$\frac{1}{1-ax}、e^{ax}$的时候已经有这种操作了)
    $$
    f(n,i)(k-i)!=\sum_{j=0}^{i-1} f(n-1,j)2^j(k-j)!,设g(n,i)=f(n,i)(k-i)! \\
    巧妙地把2放里面,G_n(x)=G_{n-1}(2x)*(e^x-1)=\prod_{j=0}^{i-1}(e^{2^jx}-1)\\
    G_{2i}=G_i(x)G_i(2^ix),倍增即可,O(nlogn)
    $$

  4. 贝尔数的生成函数

    稍微思考一下就知道是$e^{e^x-1}$,上标是个EGF,下面的exp表示组合起来;不过让我们练习一下怎么用递推式推导
    $$
    思考递推式B_n=\sum_{i=1}^nC_{n-1}^{i-1}B_{n-i},不难推出Bell的生成函数B满足 B * e^x=B’ \\
    \int \frac{B’}{B}=\int e^x,lnB=e^x+C,B=e^{e^x+C}
    又因为B(0)=1,B=e^{e^x-1} \\
    $$

  5. 带标号无向连通图生成函数F,无向图生成函数G,例题:集训队作业2013 城市规划
    $$
    g_n=\sum_{i=1}^n C_{n-1}^{i-1}f_ig_{n-i},g_n\frac{x^{n-1}}{(n-1)!}=\sum_{i=1}^n f_i\frac{x^{i-1}}{(i-1)!}*g_{n-i}\frac{x^{n-i}}{(n-i)!}\\
    G’=F’*G,lnG=F+C,带入知C=-1,F=lnG+1
    $$

  6. 三种简单背包计数,例题:luogu4389 付公主的背包
    $$
    Q1:体积为i(1… n)的物品有a_i种,每种物品无限个 \\
    Q2:体积为i(1… n)的物品有a_i种,每种物品1个 \\
    Q3:n种物品,第i种体积为a_i \\
    只需要求出\%x^n即可,大致思路:用exp和ln辅助推式子 \\
    exp内,枚举第k种,然后发现有值的位置满足调和级数,复杂度nlogn
    $$

分拆数与五边形数

就是整数无序拆分,1+2和2+1是一种方案,裸题loj6268

附做题常用:$B(20)=2e2,B(40)=4e4,B(50)=2e5,B(60)=1e6,B(70)=4e6,B(80)=2e7$

如果要求拆分的数不能相同,则最多选根号种数,预处理$O(n \sqrt n)$

然后可重复的话只能$O(n \sqrt n)$ 回答单组询问,$O(n^2)$的DP见套路集锦,还挺常用的

当然你可以用上面背包+lnexp做,但常数较大,下面介绍方法只要求逆:

设分拆数p(x)的生成函数 $P(x)=\prod_{i=1}^{\infty} \frac{1}{1-x^i}$ 总长是n方的,不能直接算

引入五边形数定理:$\prod_{i=1}^{\infty} (1-x^i)=1+\sum_{k=1}^{\infty} (-1)^kx^{k(3k \pm 1)/2}$,正负号位置都有系数

这玩意的证明自gdoi2018后不少:begay,cty,wiki

于是这个分母多项式有值的项只有根号个,可以 $n \sqrt n$ 手动求逆元,当然也可以NTT优化

不需要背,考场上打个表,很容易找规律

记录一个小技巧

$$
i(n-i)拆卷积=i(n-i)=C_{n}^2-C_{i}^2-C_{n-i}^2,考虑为两个点集间的边显然 \\
准确地说应该是这种形式:a^{i(n-i)}=a^{C_n^2-C_{i}^2-C_{n-i}^2}
$$

来自loj2409「THUPC2017」小L的计算题的一个式子

$$
对于s \in[0,m]计算 f_s=\sum_{i=1}^n a_i^s \\
这种很可能求同时求多个答案的问题考虑其生成函数
F=\sum_{i=0}^{\infty}\sum_{j=1}^n (a_jx)^i
=\sum_{i=1}^n (1-a_ix)^{-1} \\
这玩意考虑通分的话和分治FFT很像,所以应该可以搞个多项式分数的结构体,巨大常数O(nlog^2n) \\
看到分母考虑ln的导数,我们知道ln’(1-ax)=\frac{-a}{1-ax},形式很像,考虑怎么套过去(记住这个后面以后推) \\
(1-a_ix)^{-1}=1+\frac{a_ix}{1-a_ix},F=n-x\sum ln’(1-a_ix)=n-x*ln’[\prod_{i=1}^n(1-a_ix)] \\
复杂度还是O(nlog^2n),但常数小
$$

并没有增加啥新东西但似乎蛮多人做的:luogu4705玩游戏,所以大概也不是很新的科技了,只是我孤陋寡闻

目前我知道的一个应用是「清华集训2017」生成树计数,而且这式子很明显还挺容易出现的


不是所有推出来的东西都能用牛顿迭代搞,下面给出两个解决办法

拉格朗日反演

鏼爷在WC2015上的营员交流有这玩意,学习一下

zjt的博客非常详细,然而现在挂了……借助快照抄一抄

首先是一些抽象代数的知识:

通常遇到的幂级数称为F(复数域、模p数域)下的形式幂级数环$F[[x]]$

但是这并不是)(特殊的环,不同在于要求除零元外都有乘法逆元)

因此我们定义一个叫分式环的域$F((x))$

然后我们考虑这会发生什么,一个多项式A如果不是零元,就可以表示为$x^tB$而B存在乘法逆元,对这个逆元$*x^{-t}$ 就是A的逆元,所以只要我们允许x的负次幂,就是一个域了

复合逆:$F^{-1}(F(x))=x$ 显然要求「F常数项=0且一次项非0」据说交换是等价的,我是一个只会背结论不会证明的呆逼

拉格朗日反演(g求f的一个系数):$[x^n]F^{-1}(x)=\frac1n[x^{-1}]\frac1{F(x)^n}$ 证明1 证明2

然而为了方便运算咱还是把它整回到形式幂级数环,就用上面的东西自己推推就好了(求B只要/x):$[x^n]F^{-1}(x)=\frac1n[x^{n-1}] (F(x)/x)^{-n}$

拓展拉格朗日反演:$[x^n]G(F^{-1}(x))=\frac{1}{n}[x^{n-1}]G’(x)({F(x)/x})^n$

例题:bzoj3684 大朋友和多叉树: $F为所求,G(x)=x-\sum_{i \in D}x^i,G(F(x))=x$

求整个复合逆的类似BSGS的$O(n^2)$算法在他的ppt、论文上也有,有兴趣的可以了解一下

解微分方程

例题:「UR #3」链式反应

即现在已知简单函数$f(B)$(可能放了一些常多项式),求解$\frac{d}{dx} B=f(B)$;考虑怎么给牛顿迭代修锅

我们继续在b(倍增上一层结果)处泰勒展开,依然只需要展开两次
$$
\frac{d}{dx} B=f(B)=f(b)+f’(b)(B-b),(\frac{d}{dx} B)-B * f’(b)=f(b)-f’(b)*b \\
然后如果你对微积分很熟练的话(此话from炮姐,显然我不行),可以通过构造一些东西把右边搞好 \\
设pp=e^{- \int f’(b)dx },等式两边乘以pp可得(对于我这种菜鸡来说应该叫“根据积法则,不难验证等价”)\\
\frac{d}{dx} (B*pp)=(f(b)-f’(b)*b)pp,B=pp^{-1}*\int pp(f(b)-f’(b)*b)\ (\%x^n)
$$
于是就可以倍增了,而且我们现在推导的东西具有(应该)不错的推广意义,依然是$O(nlogn)$,当然这东西套了个exp进去……常数不敢想象

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/68d9.html
转载请注明出处,谢谢!