多项式求逆元
已知多项式F(x),求F(x)在保留前n项(当然n要是2的次幂)的情况下的逆元G(x),也就是:
F(x)G(x)≡1(modxn)
首先,如果n=1,那么直接就是常数项的逆元,
如果n>1,那么怎么办?
设:G′(x)使得F(x)G′(x)≡1(modxn/2),且我们已知G′(x)
第一个式子可以变成:F(x)G(x)≡1(modxn/2)
(把模数开了个方,依旧成立)
把两个式子相减:
F(x)(G(x)−G′(x))≡0(modxn/2)
G(x)−G′(x)≡0(modxn/2)
同时平方:(当然模数也平方依旧成立)
(G(x)−G′(x))2≡0(modxn)
G2(x)+G′2(x)−2G(x)G′(x)≡0(modxn)
两边同时乘上F(x),消掉部分G(x):
G(x)+G′2(x)F(x)−2G′(x)≡0(modxn)
G(x)≡2G′(x)−G′2(x)F(x)(modxn)
那么,G(x)就可以快速求出了,
(同时发现,只要常数项有逆元,这个多项式就有逆元)
复杂度:T(n)=T(n/2)+O(nlog(n))=O(nlog(n))
多项式开方
多项式的开方同样可以以这种方法做出来,
已知多项式F(x),求F(x)在保留前n项(当然n要是2的次幂)的情况下的平方根G(x),也就是:
G2(x)≡F(x)(modxn)
首先,如果n=1,那么直接就是常数项的开方,可以暴力枚举,也可以用二次项剩余(CZY的二次剩余Cipolla算法学习小记),
对于n>1的情况,
设:G′(x)使得G′(x)2≡F(x)(modxn/2),且我们已知G′(x),
(把平方写在后面好看QuQ)
第一个式子可以变成:G2(x)≡F(x)(modxn/2)
(把模数开了个方,依旧成立)
把两个式子相减:
G2(x)−G′(x)2≡0(modxn/2)
因式分解:
(G(x)+G′(x))(G(x)−G′(x))≡0(modxn/2)
可得G(x)有两个解(平方嘛),讨论G(x)−G′(x)≡0(modxn/2)的情况,
G(x)−G′(x)≡0(modxn/2)
(历史总是惊人的相识)
同时平方:(当然模数也平方依旧成立)
(G(x)−G′(x))2≡0(modxn)
G2(x)+G′(x)2−2G(x)G′(x)≡0(modxn)
因为:G2(x)≡F(x)(modxn)
F(x)+G′(x)2−2G(x)G′(x)≡0(modxn)
G(x)≡2G′(x)F(x)+G′(x)2(modxn)
那么,G(x)就可以快速求出了,
(同时发现,只要常数项是二次项剩余且有逆元,这个多项式就可以开方)
复杂度:T(n)=T(n/2)+2∗O(nlog(n))=O(nlog(n))
多项式取模
已知A(x),B(x),求D(x)=A(x)modB(x),
令A(x)=B(x)C(x)+D(x)
设n=A(x)的次数,m=B(x)的次数,显然有m≤n,
上面的等式两边同时乘上xn得:
xnA(x1)=xmB(x1)xn−mC(x1)+xnD(x1)
(x1的作用相当于是把多项式头尾翻转一下)
设A′(x)=xnA(x1),B′(x)=xmB(x1),C′(x)=xn−mC(x1),D′(x)=xnD(x1)
可以发现,经过翻转后,
D′(x)中只有次数∈[n−m+1,n]的项是有效的,其他项均为0,,
A′(x)中次数∈[0,n]的项是有效的,
B′(x)中次数∈[0,m]的项是有效的,
C′(x)中次数∈[0,n−m]的项是有效的,
现在再对原来的等式modxn−m+1,也就是
A′(x)=B′(x)C′(x)+D′(x)modxn−m+1
这样D′(x)这一项就能模掉了,也就是:
A′(x)=B′(x)C′(x)modxn−m+1
B′(x)A′(x)=C′(x)modxn−m+1
因为C′(x)的次数范围刚好在模以内,所以就可以直接求出C′(x),变换得C(x),
求出了C(x),剩下直接减就好了
D(x)=A(x)−B(x)C(x)
复杂度:O(nlog(n))
多项式多点求值
已知多项式F(x),给出a1,a2,...,an,要求F(a1),F(a2),...,F(an)
先抛出一个显然的结论:F(a1)=F(x)mod(x+a1),
(意思是:多项式F(x)模多项式(x+a1)的余数就是当x=a1时F(x)的值)
有这个结论就好办了,
设多项式Cl,r(x)=∏i=lr(x+ai),Gl,r(x)=F(x)modCl,r(x),
考虑分治求解,
显然的:Gl,mid(x)=Gl,r(x)modCl,r(x),右边同理,
这样当l=r时Gl,l(x)就是F(al)的值了,
做两遍分治FFT,
复杂度:O(nlog2(n))
多项式插值
给出a1,b1,a2,b2,...,ak,bk,要求多项式F(x)满足F(ai)=bi,
考虑使用拉格朗日插值法,
F(x)=i=1∑kbi(1≤j≤k,i̸=j∏ai−ajx−aj)
将式子拆成两部分:
F(x)=i=1∑kbi(1≤j≤k,i̸=j∏ai−aj1)(1≤j≤k,i̸=j∏(x−aj))
先做前面那一部分:(先取个倒数方便书写)
设Gi=∏1≤j≤k,i̸=j(ai−aj),M(x)=∏j=1k(ai−aj)
显然有M(ai)=0,
有:
Gi=x→ailimx−ajM(x)−M(ai)
我们发现这个东西相当于M(x)在x=ai处的导数,于是有:
Gi=x→ailimx−ajM(x)−M(ai)=M′(ai)
所以对M′(x)做一次多点求值即可,
这个东西还可以用洛必达法则证明,
设f(x)=x−ai
已知有limx→aiM(x)=0,limx→aif(x)=0
所以:
x→ailimf(x)M(x)=x→ailimf′(x)M′(x)=M′(ai)
现在的原始变成了:
F(x)=i=1∑kbiGi(1≤j≤k,i̸=j∏(x−aj))
这个东西可以直接使用分治FFT实现,分治的时候记录两个多项式分别表示是否已经空缺了一位,
复杂度:O(nlog2(n))
多点求值+几遍分治FFT常数爆炸
多项式牛顿迭代
已知多项式G(x),要求多项式F使得G(F)=0modxn
前置技能:
泰勒展开
对于多项式f(x)它在x0处的泰勒展开为:
f(x)=f(x0)+1!f′(x)(x−x0)+2!f′′(x)(x−x0)2+.....
考虑倍增求F
现在要求的F是modx2n的,假设我们已经求出了F0表示modxn时的答案,
把G(F)在F0处展开:
G(F)=G(F0)+G′(F0)(F−F0)+21G′′(F0)(F−F0)2modx2n
我们注意到是在modx2n意义下的,而从第3项开始最低次项的指数均大于2n,所以可以直接省去,于是:
G(F)=G(F0)+G′(F0)(F−F0)modx2n
又因为G(F)=0modx2n,
0=G(F0)+G′(F0)F−G′(F0)F0modx2n
F=F0−G′(F0)G(F0)
多项式求对数
给出多项式G(x),要求F(x)使得F(x)=ln(G(x))modxn
对两边同时求导,最后再积分回来,
有:
(ln(G(x)))′=G(x)G′(x)
所以
F(x)=∫G(x)G′(x)dx
复杂度:O(nlog(n))
多项式求EXP
给出多项式G(x),求F(x)满足F(x)=eG(x),
考虑使用牛顿迭代,
设多项式g(x)=ln(x)−G(x),即g(F)=0
F=F0−g′(F0)g(F0)
又因为
g′(F0)=(ln(F0))′−(A)′=F01
所以:
F=F0−F0(ln(F0)−A)
复杂度:O(nlog(n))
多项式求幂
给出多项式F(x),求F(x)k,
F(x)k=ekln(F(x))
这样如果k不为整数也能求了
复杂度:O(nlog(n))