多项式求逆

Procedure

多项式求逆是多项式模块中的一个重要操作（“操作”这个词看出如今多项式题是多么的工业化，犹如毒瘤8操作LCT）,在做生成函数/多项式除法、多项式取模/多项式多点求值等中均有应用 对于一个n次多项式$F(x)$，我们希望求出一个m-1次多项式$G(x)$，满足$F(x)G(x)equiv 1pmod {x^m}$
也就是说，$G(x)$为$F(x)$在模$x^m$意义下的逆（即$x^m$以后的项我们都不管了，前面的项乘起来只有常数项系数为1，其他系数都是0） 多项式求逆运用了倍增的思想
假设我们已经求出了$B(x),B(x)F(x)equiv 1pmod {x^{mover 2}}$
考虑如何求$G(x)$ 移项
$B(x)F(x)-1equiv 0pmod {x^{mover 2}}$
此时意味着$B(x)F(x)-1$的0 ~ m/2-1次项的系数全都是0，那么将同余式两边平方，就变成0 ~ m-1次项的系数都为0
因此
$left(B(x)F(x)-1 ight)^2equiv 0 pmod {x^m}$
展开
$F^2(x)B^2(x)-2F(x)B(x)+1equiv 0pmod {x^m}$
提一个$F(x)$出来
$F(x)left(F(x)B^2(x)-2B(x) ight)equiv -1pmod {x^m}$ 此时容易看出$G(x)equiv 2B(x)-F(x)B^2(x) pmod {x^m}$
这样就求出了$F(x)$模$x^m$意义下的乘法逆元
我们从m=1开始做，此时直接求常数项的乘法逆元即可，
然后可以推出m=2,4,8,16…
这样一直倍增下去，直到m>=我们所需要的次数，此时直接取前面我们需要的项，后面多出来的直接设为0即可（模掉了没有影响） 注意，由于我们求$G(x)$是在模$x^m$意义下进行的，而不是$x^{mover 2}$，因此即使$B(x)$的次数为m/2-1，此时的$F(x)$的次数仍然要取m-1 分析时间复杂度
$T(n)=T(n/2)+O(nlog n)=O(nlog n)$（常数相当大）

Code

void make(int l,LL *a,LL *b)//l为我们需要的次数，a为待求逆多项式，用b来存储结果 { b[0]=ksm(a[0],mo-2);//求常数项逆元 for(int m=1,t=2,num=4,cnt=2;m<l;m=t,t=num,num<<=1,cnt++) //由于乘法有平方操作，因此NTT的范围需要开到2倍。 //t为当前的模数次数,m=t/2 { prp(num,cnt);//预处理单位根、反位等 fo(i,0,m-1) c[i]=a[i],d[i]=b[i]; fo(i,m,t-1) c[i]=a[i]; fo(i,t,num-1) c[i]=0; NTT(c,0,num),NTT(b,0,num); fo(i,0,num-1) b[i]=b[i]*b[i]%mo*c[i]%mo; NTT(b,1,num); fo(i,0,t-1) b[i]=((LL)2*d[i]-b[i]+mo)%mo; fo(i,t,num-1) b[i]=0; } }

多项式除法（多项式取模）

Procedure

多项式除法/取模也是多项式模块中的一个重要操作，在做生成函数/多项式多点求值等中均有应用。。。
对于一个n次多项式$F(x)$，m次多项式$G(x)$(n>=m)，我们希望求出一个n-m次多项式$H(x)$，一个至多m-1次的多项式$R(x)$，满足$F(x)=G(x)H(x)+R(x)$，并且$R(x)$小于$G(x)$ 当$R(x)equiv 0pmod {x^{n-m+1}}$时，我们就可以直接对$G(x)$求逆了
接下来的方法就比较高妙了： 我们引入多项式的反转操作，即将多项式的系数倒转过来
形式化的，对于n次多项式$F(x)$，反转之后就是$x^nFleft({1over x} ight)$ 对于上面的等式反转
$x^nFleft({1over x} ight)=x^n(Gleft({1over x} ight)Hleft({1over x} ight)+Rleft({1over x} ight))$ 此时相当于将x替换成1/x，等式仍然成立
右边分配x^n