多项式&生成函数学习笔记

前言

对多项式和生成函数的一些学习。

多项式题目

[ZJOI2014]力

Description

$\begin{aligned} &F(j)=\sum_{i=1}^{j-1}\frac{q_i\times q_j}{(i-j)^2}-\sum_{i=j+1}^n\frac{q_i\times q_j}{(i-j)^2}\\ &E(j)=\frac{F(j)}{q(j)} \end{aligned}$

给定$q$，求$e$

Solution

大力推即可。

$\begin{aligned} &E(j)=\sum_{i=1}^{j-1}\frac{q_i}{(i-j)^2}-\sum_{i=j+1}^n\frac{q_i}{(i-j)^2}\\ \end{aligned}$

令$f(i)=q_i$ $g(i)=\frac{1}{i^2}$

即

$\begin{aligned} E(j)&=\sum_{i=0}^{j}f(i)g(j-i)-\sum_{i=j}^nf(i)g(i-j)\\ \end{aligned}$

左边直接卷！

右边根据套路反转，即$g'(i)=g(n-i)$

$\begin{aligned} &\sum_{i=j}^nf(i)g'(n-i+j)\\ =&\sum_{i=0}^{n-j}f(i)g'(n-i) \end{aligned}$

卷！

城市规划

Description

无标号联通无向图数量。

Solution

设答案为$f(n)$,设$g(n)$为$n$个点的无向图数量。

不难发现$g(n)=2^{\binom{n}{2}}$

考虑枚举第一个节点所在连通块大小，既有式子

$g(n)=\sum_{i=0}^nf(i)\binom{n-1}{i-1}g(n-i)$

把组合数拆一下。

$\begin{aligned} g(n)&=\sum_{i=0}^nf(i)\binom{n-1}{i-1}g(n-i)\\ g(n)&=\sum_{i=0}^nf(i)\frac{(n-1)!}{(i-1)!(n-i)!}g(n-i)\\ \frac{g(n)}{(n-1)!}&=\sum_{i=0}^nf(i)\frac{1}{(i-1)!(n-i)!}g(n-i) \end{aligned}$

看起来没思路了（

但是观察一下发现

$\begin{aligned} \frac{g(n)}{(n-1)!}&=\sum_{i=0}^nf(i)\frac{1}{(i-1)!(n-i)!}g(n-i)\\ \frac{g(n)}{(n-1)!}&=\sum_{i=0}^n\frac{f(i)}{(i-1)!}\times\frac{g(n-i)}{(n-i)!} \end{aligned}$

每项只和当前相关，后两项还是一个明显的卷积形式。

卷！

残缺的字符串

Description

通配符字符串匹配问题。

Solution

我们设计一个匹配函数用来进行匹配。

我们假设$F(x,y)=a(x)-b(y)$为了避免正负符号问题，我们将其平方。

这样两个相同的位置一定是0，否则只要有一个不匹配的，平方后为正数，不符合我们要匹配为0。

因此将通配符的值全变为0。

我们对于一个位置$x$是否能匹配，发现就是

$F(x)=\sum_{i=0}^{m-1} (a_{x-m+i+1}-b_{m-i-1})^2a_{x-m+i+1}b_{m-i-1}$

用小$trick$将$b$反转之后。

$\begin{aligned} F(x)&=\sum_{i=0}^{m-1} (a_{x-m+i+1}-b_{i})^2a_{x-m+i+1}b_{i}\\ &=\sum_{i=0}^{m-1}a_{x-m+i+1}^3br_{m-i-1}+\sum_{i=0}^{m-1}br_{m-i-1}^3a_{x-m+i+1}-2\sum_{i=0}^{m-1}a_{x-m+i+1}^2br_{m-i-1}^2\\ \end{aligned}$

卷！

Fuzzy Search

Description

点开吧

Solution

这题多了个扩展匹配。

由于只有$ATCG$四种碱基，分别考虑。

对可以扩展的位置变成当前考虑的这个字符，跑上面的通配符字符串匹配即可。

对式子进行一番化简。

卷！

[AH2017/HNOI2017]礼物

Description

经典题呢。

Solution

设对$a$串增加$c$，并且已经将$b$反转后

答案为

$\begin{aligned} &\sum_{i=1}^n(a_i-b_i+c)^2\\ =&\sum_{i=1}^na_i^2+\sum_{i=1}^nb_i^2+2c(\sum_{i=1}^na_i-\sum_{i=1}^nb_i)+nc^2-2\sum_{i=1}^na_ib_i\\ \end{aligned}$

前面两项固定，后两项是关于$c$的二次函数求最值。

因此要最大化$\sum_{i=1}^na_ib_i$

由于反转，破环成链，再再再利用小$trick$将b反转之后

卷！

生成函数

定义

生成函数是相对数列而言，一个数列$\left<a_1,a_2,a_3...\right>$的普通生成函数为$F(x)=\sum_{i=0}^{\infty}a_ix^i$

其指数生成函数为$\hat{G(x)}=\sum_{i=0}^\infty \frac{a_i}{i!}x^i$

使用生成函数可以有许多美妙的变换。

基本生成函数

$\begin{aligned} &\left<1,1,1,1,1...\right>=\frac{1}{1-x}\\ &\left<1,-1,1,-1...\right>=\frac{1}{1+x}\\ &\left<1,2,3,4,5...\right>=\frac{1}{(1-x)^2}\\ &\left<1,0,1,0,1...\right>=\frac{1}{1-x^2}\\ &\left<1,0,...0,1,0,...0,1...\right>=\frac{1}{1-x^m}\\ &\left<1,2,4,8,16,32\right>=\frac{1}{1-2x}\\ &\left<1,c^2,c^3,c^4...\right>=\frac{1}{1-cx}\\ &\left<1,\binom{c}{1},\binom{c}{2},\binom{c}{3}... \right>=\frac{1}{(1+z)^c}\\ &\left<1,\binom{c}{1},-\binom{c}{2},\binom{c}{3}... \right>=\frac{1}{(1-z)^c}\\ &\left<1,\binom{m+1}{1},\binom{m+2}{2},\binom{m+3}{3}... \right>=\frac{1}{(1-z)^{m+1}}\\ &\left<0,1,\frac{1}{2},\frac{1}{2},\frac{1}{3}... \right>=\ln\frac{1}{1-z}\\ &\left<011,\frac{1}{2},-\frac{1}{2},\frac{1}{3}... \right>=\ln{1+z}\\ &\left<1,1,\frac{1}{2},\frac{1}{6},\frac{1}{24}\frac{1}{120}... \right>=e^z\\ \end{aligned}$

指数生成函数

也叫$EGF$，名字来源于上表最后一个生成函数为$\left<1,1,1...\right>$的指数生成函数，为$e^z$

下降幂多项式乘法

我们考虑一个多项式的点值的$EGF$

为

$\begin{aligned} \hat G(x)=\sum_{i=0}^\infty \frac{F(i)}{i!}x^i \end{aligned}$

考虑一个下降幂单项式$x^{\underline{n}}$其点值的生成函数为

$\begin{aligned} \hat G_n(x)&=\sum_{i=0}^\infty\frac{i^{\underline{n}}}{i!}x^i\\ &=\sum_{i=0}^\infty\frac{1}{(i-n)!}x^i\\ &=\sum_{i=0}^\infty\frac{x^{n+i}}{i!}\\ &=x^n\sum_{i=0}^\infty\frac{x^i}{i!}\\ &=x^ne^x \end{aligned}$

则

$\begin{aligned} \hat G(x)&=\sum_{i=0}^\infty f_i\hat G_i(x)\\ &=e^x\sum_{i=0}^\infty f_ix^i\\ &=e^xG(x) \end{aligned}$

合理！

因此对下降幂求点值只需把他和$e^x$卷一下即可。

生成函数的基本运算

有一些在推式子时会用到的。

以下的生成函数为$\left<g_n\right>$的生成函数

$\begin{aligned} z^mG(z)&=\sum_{n}g_{n-m}x^n\\ G(cz)&=\sum_{n}c^ng_nz^n\\ G'(z)&=\sum_n(n+1)g_{n+1}z^n\\ \int G(z)dt&= \sum_n\frac{1}{n}g_{n-1}z^n\\ \alpha F(z)+\beta G(z) &=\sum_n(\alpha f_n+\beta g_n)x^n\\ \end{aligned}$

还非常有用的是对生成函数$F(z)=\frac{1}{1-z}$做卷积，相当于自己的前缀和。

特殊的生成函数

这里建议直接背诵

斐波那契生成函数

$F(z)=\frac{z}{1-z-z^2}$

卡特兰数生成函数

$C(z)=zC^2(z)+1$

这个不完全是封闭形式，运用求根公式可以展开。

例题

付公主的背包

Description

有$n$种物品，每种物品体积为$v$，每种商品有无数个，求凑出体积为$m$的方案数。

Solution

这就是生成函数最基本的应用。

显然对于每个物品我们知道他的生成函数长这样

$F(x)=\sum_{i=0}^{\infty}x^{v\times i}=\frac{1}{1-x^v}$

暴力来做就把这$n$个生成函数卷起来就行了。

考虑优化。在麦克劳林级数定义下的$\ln$可以进行正常运算，我们可以把卷积这种复杂度较高的式子优化为加法。

设 $G(x)=\ln(F(x))$

大力推就好了。

$\begin{aligned} G'(x)&=\ln'(F(x))\\ G'(x)&=\frac{F'(x)}{F(x)}\\ \frac{F'(x)}{F(x)}&=F'(x)(1-x^v)\\ &=\sum_{i=0}^{\infty}vix^{vi-1}(1-x^v)\\ &=\sum_{i=0}^{\infty}vix^{vi-1}-\sum_{i=0}^{\infty}vix^{v(i+1)-1}\\ &=\sum_{i=1}^{\infty}vix^{vi-1}-\sum_{i=1}^{\infty}v(i-1)x^{vi-1}\\ &=\sum_{i=1}^{\infty}vx^{vi-1}=G'(x)\\ \int G'(x)dx&=\sum_{i=1}^{\infty}\frac{x^{vi}}{i} \end{aligned}$

答案就是

$e^{\sum_{i=1}^nG(x)}$

多项式 $exp$ 即可，总复杂度 $O(m\log m)$

The Child and Binary Tree

Description

给定$n$种节点，每种节点都有一个权值，一棵二叉树的权值为每个节点的权值的和，求权值为$1-m$的不同的二叉树的数量。

Solution

众所周知，对于无标号无权值的二叉树计数就是卡特兰数。

我们已知卡特兰数的生成函数是

$C(x)=xC^2(x)+1$

其中这个$x$的每个节点权值都为$1$，直接做即可，到这道题上，我们可以构造出点集的生成函数，不难发现是

$W(x)=\sum_{i=1}^n x^{c_i}$

映射到数列上就是

$\left< 1,0,0 ...1,0,0...1... \right>$

的数列，其中间隔的长度是点集中的数的权值。

将 $W(x)$ 带回原先的卡特兰数的式子即可。

答案为

$\begin{aligned} F(x)&=W(x)F^2(x)+1\\ &=\frac{1-\sqrt{1-4W(x)}}{2W(x)} \end{aligned}$

关于另一个取$+$的根，感性理解当$\lim_{x->0}$的时候，取正值为正无穷，因此不能取。

（不过我建议两个都试一下看哪个能过样例。

差分与前缀和

Description

求给定数列的$k$阶差分$/5Solution

数列，$k$阶前缀和，要素察觉。

不难发现求前缀和的数列时答案就是$F*(\frac{1}{1-x})^k$

这是我们通过已经知道的前缀和生成函数卷出来的结果。

现在考虑在未知差分生成函数的情况下，如何写出其生成函数。

考虑原式的意义。

做一次前缀和，及卷上生成函数$F(z)=\sum_{i}^\infty x^i$

他的数列是$\left<1,1,1,1,1,1,1...\right>$，相当于对于每一项，向他后面的所有项都贡献当前点的价值。

前缀和就是当前项向后一项贡献当前点的负价值，那么不难发现其生成函数就是$F(z)=1-z$

在卷一遍即可。

Super Poker II

Description

只能做水题人。

Solution

不难发现将四种牌每个的生成函数写出来。

输入的不能取的去掉。

把四个生成函数卷起来就行了/kk