(暴力)多项式与生成函数_成型笔记
JueFan 一只绝帆

多项式与生成函数

由于快速傅里叶变换并不在 CCF 的考纲之内,故对于多项式的考察仅限于公式推导。

即使是只剩下公式推导,多项式仍然是一个强大的工具。

多项式暴力全家桶

以下很多东西是在  mod  xc\bmod\ x^c 意义下定义的,不过推导过程并不需要用到 cc,比较神奇。

加法 数乘 卷积

暴力模拟即可。

加法复杂度 max⁡(n,m)\max(n,m),数乘复杂度 nn,卷积复杂度 nmnm。

求导

ai′=(i+1)ai+1a'_i=(i+1)a_{i+1},注意这会丢掉常数项。

积分

ai′=ai−1ia'_i=\frac{a_{i-1}}{i}。

求逆

其实就是 ∀n,∑iAiBn−i=[n=0]\forall n,\sum_iA_iB_{n-i}=[n=0]。

不妨设 n>0n>0,把 A0A_0 拿出来:

A0Bn=−∑i=1nAiBn−iBn=−∑i=1nAiBn−iA0A_0B_n=-\sum_{i=1}^nA_iB_{n-i}\\B_n=\frac{-\sum_{i=1}^nA_iB_{n-i}}{A_0}

边界是 B0=1A0B_0=\frac{1}{A_0},这也告诉我们多项式存在逆的条件是 A0≠0A_0\ne0。

递推即可,复杂度 O(cn)\cal O(cn)(cc 为模数 xcx^c 的指数),这也告诉我们两个多项式相除复杂度必须至少是分母的平方。

多项式相除就是多计算一次卷积,复杂度 O(cn+cm)\cal O(cn+cm)。

实际上我们不必求逆再相乘,可以进一步求多项式除法:

∀n,∑iAi(BA)n−i=BnA0(BA)n=Bn−∑i=1nAi(BA)n−i(BA)n=Bn−∑i=1nAi(BA)n−iA0\forall n,\sum_{i}A_i({\frac BA})_{n-i}=B_n\\A_0(\frac B A)_n=B_n-\sum_{i=1}^nA_i(\frac B A)_{n-i}\\(\frac B A)_n=\frac{B_n-\sum_{i=1}^nA_i(\frac{B}{A})_{n-i}}{A_0}

然后你发现这个东西就变成 O(cm)\cal O(cm)(mm 为分母次数)的了,这也告诉我们多项式除单项式还是能做的。

你可能会举出退背包的例子告诉我这可以做到 O(nm)\cal O(nm),那岂不是求逆复杂度直接变成 O(n)\cal O(n),乐。

事实上这里的退背包取决于你想要多长的数组,也就是 cc,你至少要保证答案数组长度 ≤c\le c。

ln/exp

注意多项式存在 ln⁡\ln 的条件是 [x0]F(x)=1[x^0]F(x)=1,小时候看这集兴奋地说解决了离散对数求解难题。

多项式存在 exp⁡\exp 的条件是 [x0]F(x)=0[x^0]F(x)=0。

令 G(z)=ln⁡F(z)G(z)=\ln F(z),对两边求导,得:

G′(z)=F′(z)F(z),G(z)=∫dzF′(z)F(z)G'(z)=\frac{F'(z)}{F(z)},G(z)=\int \text{d}z\frac{F'(z)}{F(z)}

令 G(z)=exp⁡F(z)G(z)=\exp F(z),两边求导,得:

G′(z)=G(z)F′(z)G'(z)=G(z)F'(z)

展开 F(x),G(x)F(x),G(x) 系数序列为 A,BA,B:

(n+1)Bn+1=∑i=0nBn−i(i+1)Ai+1Bn=1n∑i=1niAiBn−i\begin{aligned}(n+1)B_{n+1}&=\sum_{i=0}^nB_{n-i}(i+1)A_{i+1}\\B_n&=\frac 1 n\sum_{i=1}^niA_iB_{n-i}\end{aligned}

 评论
评论插件加载失败
正在加载评论插件
由 Hexo 驱动 & 主题 Keep
总字数 237.9k 访客数 访问量