多项式全家桶

有一说一，感觉之前写的其实都是写不重要或特别基础的东东。 现在才是一些比较有难度的东东。

多项式求逆即为求一个多项式的乘法逆元。 它长这样： A ( x ) ∗ B ( x ) ≡ 1 ( m o d   x n ) A(x)*B(x)\equiv 1(mod\ x^n) A(x)∗B(x)≡1(mod xn) 然后多项式 B ( x ) B(x) B(x)就叫做多项式 A ( x ) A(x) A(x)的逆元。 这玩意和普通的乘法逆元有一点不同的就是，它的模是一个 x n x^n xn，其意义为把结果中次数大于等于n的项都给忽略掉。

引理一： 考虑一个乘法逆元满足： A ( x ) ∗ B ( x ) ≡ 1 ( m o d   x n ) A(x)*B(x)\equiv 1(mod\ x^n) A(x)∗B(x)≡1(mod xn)，那么我们可以得到另一个柿子： A ( x ) ∗ B ( x ) ≡ 1 ( m o d   x m ) A(x)*B(x)\equiv 1(mod\ x^m) A(x)∗B(x)≡1(mod xm)其中 1 < = m < = n 1 if ((b&1)==1) t=t*y%mo; y=y*y%mo; b/=2; } return t; } void FFT(long long a[],int n,int inv) { if (n==1) return; int mid=n/2; for (int i=0;i int mid=len/2; for (int j=0;j int p,q; q=w[j*(n/len)]*a[k+mid]%mo,p=a[k]; a[k+mid]=(p-q+mo)%mo; a[k]=(p+q+mo)%mo; } } } } void solve(int n) { if (n==1) { b[0]=qsm(a[0],mo-2); } else { double op=n; int oq=ceil(op/2); solve(oq); up=1;dep=0; while (up A[i]=G[i]*(2-A[i]*G[i]%mo+mo)%mo; } for (int i=0;i scanf("%d",&n); jl=n; for (int i=0;i printf("%lld ",b[i]); } printf("\n"); } 多项式除法 介绍

这玩意是求一个长成这样的柿子的： A ( x ) = B ( x ) ∗ D ( x ) + R ( x ) A(x)=B(x)*D(x)+R(x) A(x)=B(x)∗D(x)+R(x) 其中 A ( x ) A(x) A(x)和 B ( x ) B(x) B(x)已经给出，且 A ( x ) A(x) A(x)次数为n， B ( x ) B(x) B(x)次数为m，求 D ( x ) D(x) D(x)和 R ( x ) R(x) R(x) 也就是除法运算中求商和余数，话说如果上过初中就应该明白长除法。

引理二： 考虑一个反转操作为将一个多项式的系数调换，用数学形式表达即为： P r ( x ) = x n ∗ P ( 1 x ) = ∑ i = 0 n a n − i ∗ x i Pr(x)=x^n*P(\frac 1 x)=\sum_{i=0}^n a_{n-i}*x^i Pr(x)=xn∗P(x1​)=i=0∑n​an−i​∗xi 证明显然。

那么现在就推柿子： A ( x ) = B ( x ) D ( x ) + R ( x ) A ( 1 x ) = B ( 1 x ) D ( 1 x ) + R ( 1 x ) x n A ( 1 x ) = x n B ( 1 x ) D ( 1 x ) + x n R ( x ) x n A ( 1 x ) = x m B ( 1 x ) x n − m D ( 1 x ) + x n − m + 1 x m − 1 R ( x ) A(x)=B(x)D(x)+R(x)\\A(\frac 1 x)=B(\frac 1 x)D(\frac 1 x)+R(\frac 1 x)\\x^nA(\frac 1 x)=x^nB(\frac 1 x)D(\frac 1 x)+x^nR(x)\\x^nA(\frac 1 x)=x^mB(\frac 1 x)x^{n-m}D(\frac 1 x)+x^{n-m+1}x^{m-1}R(x) A(x)=B(x)D(x)+R(x)A(x1​)=B(x1​)D(x1​)+R(x1​)xnA(x1​)=xnB(x1​)D(x1​)+xnR(x)xnA(x1​)=xmB(x1​)xn−mD(x1​)+xn−m+1xm−1R(x) 然后再引入引理： A r ( x ) = B r ( x ) D r ( x ) + x n − m + 1 R r ( x ) Ar(x)=Br(x)Dr(x)+x^{n-m+1}Rr(x) Ar(x)=Br(x)Dr(x)+xn−m+1Rr(x) 由于我们的 D r ( x ) Dr(x) Dr(x)的次数是小于等于 n − m n-m n−m的，所以如果对原式取模只要大于之即可，而 A ( x ) A(x) A(x)、 B ( x ) B(x) B(x)都已知，所以不必理会。 A r ( x ) ≡ B r ( x ) D r ( x ) ( m o d   x n − m + 1 ) Ar(x)\equiv Br(x)Dr(x)(mod\ x^{n-m+1}) Ar(x)≡Br(x)Dr(x)(mod xn−m+1) 然后我们就可以直接求 B r ( x ) Br(x) Br(x)的逆元，再乘 A r ( x ) Ar(x) Ar(x)即可得到 D r ( x ) Dr(x) Dr(x)，再把系数反过来即可求出 D ( x ) D(x) D(x)。

当然，求出 D ( x ) D(x) D(x)之后，再求 R ( x ) R(x) R(x)就很简单了。

学习资料 https://www.cnblogs.com/knife-rose/p/12056617.html https://www.cnblogs.com/owenyu/p/6724611.html