多项式各种操作（求逆，取模，ln，exp，开方，牛顿迭代）+生成函数

2019-04-13 15:53发布

站内文章 / 模拟电子
16967 0 1759
我们已经知道了可以使用FFT和NTT在O(nlogn)O(nlogn)的时间内计算多项式乘法，那对于其它的运算呢？
首先，我们需要知道多项式逆元这个根本性的问题。

多项式求逆

考虑两个多项式A(x)，B(x)，若A(x)B(x)≡1(mod xn)A(x)，B(x)，若A(x)B(x)equiv 1(mod~x^n)，那么我们称B(x)是A(x)mod xnB(x)是A(x)mod~x^n意义下的逆元，即它们乘积的前nn项只有常数项为1，其它都是0.
那么我们如何计算逆元呢？考虑如果我们已经计算出了A(x)C(x)≡1(mod xn)A(x)C(x)equiv 1(mod~x^n)，那么我们能不能推导出满足A(x)B(x)≡1(mod x2n)A(x)B(x)equiv 1(mod~x^{2n})的多项式B(x)B(x)呢？
首先将两式相减，可以得到
A(x)(B(x)−C(x))≡0(mod xn)A(x)(B(x)-C(x))equiv0(mod~x^n)
由于等式左边多项式的前nn项系数都是0，可以把这个玩意儿平方：
A2(x)B2(x)+A2(x)C2(x)−2A2(x)B(x)C(x)≡0(mod x2n)A^2(x)B^2(x)+A^2(x)C^2(x)-2A^2(x)B(x)C(x)equiv0(mod~x^{2n})
又由于A(x)B(x)≡1(mod x2n)A(x)B(x)equiv 1(mod~x^{2n})，带入可以得到：
2A(x)C(x)−A2(x)C2(x)≡1(mod x2n)2A(x)C(x)-A^2(x)C^2(x)equiv1(mod~x^{2n})
提取多项式A(x)A(x)：
A(x)(2C(x)−A(x)C2(x))≡1(mod x2n)A(x)(2C(x)-A(x)C^2(x))equiv1(mod~x^{2n})
即B(x)=2C(x)−A(x)C2(x)B(x)=2C(x)-A(x)C^2(x)。
于是我们会发现一个多项式是否有逆元完全取决于该多项式的常数项是否有逆元。由于这个算法每次可以将问题规模减半，总的时间复杂度就是T(n)=T(n2)+O(nlogn)=O(nlogn)T(n)=T(frac n2)+O(nlogn)=O(nlogn)

例题 洛谷3711 仓鼠的数学题

题目链接
首先可以想到使用伯努利数来化简算式。于是就有
f(n)=∑k=0nSk(x)ak=1+∑k=0nak1k+1∑i=0k(−1)i(k+1i)Bixk+1−if(n)=sum_{k=0}^nS_k(x)a_k=1+sum_{k=0}^na_kfrac{1}{k+1}sum_{i=0}^k(-1)^iinom{k+1}{i}B_ix^{k+1-i}
最开始有个1是因为题目中把000^0也算为1.然后我们考虑继续化简：
f(n)−1=∑i=0n(−1)ii!∑k=inakBixk+1−ik!(k+1−i)!f(n)-1=sum_{i=0}^nfrac{(-1)^i}{i!}sum_{k=i}^nfrac{a_kB_ix^{k+1-i}k!}{(k+1-i)!}
由于我们要求的是多项式，考虑枚举x的指数：
f(n)−1=∑i=1n+1xii!∑k=0n+1−i(−1)kBk(i+k−1)!k!f(n)-1=sum_{i=1}^{n+1}frac{x^i}{i!}sum_{k=0}^{n+1-i}frac{(-1)^kB_k(i+k-1)!}{k!}
然后就是很经典的翻转卷积模型了。
令A(k)=(−1)kBkk!，B(k)=(n−k)!，则f(n)−1=∑i=1n+1xii!∑k=0n+1−iA(k)B(n+1−i−k)令A(k)=frac{(-1)^kB_k}{k!}，B(k)=(n-k)!，则f(n)-1=sum_{i=1}^{n+1}frac{x^i}{i!}sum_{k=0}^{n+1-i}A(k)B(n+1-i-k)

热门文章