多项式除法及取模
介绍
首先你需要会多项式求逆，可参考另一篇博文。
多项式除法和多项式取模有很多应用，比如线性递推的优化，多项式多点求值和多点插值。
基本概念
对于一个多项式 A(x)A(x)A(x) ，称其最高项的次数为 A(x)A(x)A(x) 的度 ，记作 degAdegAdegA 。
对于多项式 A(x),B(x)A(x),B(x)A(x),B(x) ，存在唯一的 Q(x),R(x)Q(x),R(x)Q(x),R(x) 满足 A(x)=Q(x)B(x)+R(x)A(x)=Q(x)B(x)+R(x)A(x)=Q(x)B(x)+R(x) ，且 degR<degBdegR<degBdegR<degB ，我们称 Q(x)Q(x)Q(x) 为 B(x)B(x)B(x) 除 A(x)A(x)A(x) 的商 ，$R(x) $ 为 B(x)B(x)B(x) 除 A(x)A(x)A(x) 的余数，可记作 $A(x) \equiv R(x) \pmod {B(x)} $ 。
多项式除法和多项式取模就是给你 A(x),B(x)A(x),B(x)A(x),B(x) ，让你求 Q(x)Q(x)Q(x) 和 R(x)R(x)R(x) 。
基本算法
对于一个 nnn 次多项式 A(x)A(x)A(x) ，考虑下面这个变换的意义： $\displaystyle AR(x)=xnA(\frac{1}{x}) $ ，
原来的 aixia_ix^iaixi 变成了 aixn−ia_ix^{n-i}aixn−i ，因此 AR(x)A^R(x)AR(x) 相当于将 A(x)A(x)A(x) 的系数反转。
设 degA=n，degB=mdegA=n，degB=mdegA=n，degB=m 。
下面将 degRdegRdegR 看作 m−1m-1m−1 ， degQdegQdegQ 看作 n−mn-mn−m ，高次项不存在则认为是 000 。
将 A(x)=Q(x)B(x)+R(x)A(x)=Q(x)B(x)+R(x)A(x)=Q(x)B(x)+R(x) 的 xxx 用 $\displaystyle \frac{1}{x} $ 代替，然后两边同乘 xnx^nxn ，得：
$\displaystyle x^nA( \frac{1}{x} )= x{n-m}Q(\frac{1}{x})xmB(\frac{1}{x})+x{n-m+1}x{m-1} R(\frac{1}{x}) $
$ AR(x)=QR(x)BR(x)+x{n-m+1}R^R(x) $
现在，由于 degQ=n−mdegQ=n-mdegQ=n−m ，系数反转之后次数仍然不变，因此我们把上面这个式子两边对 $x^{n-m+1} $ 取模，就可以消除 R(x)R(x)R(x) 的影响了：
$A^R(x) \equiv Q^R(x) B^R(x) \pmod{x^{n-m+1}} $
这样只需要求 BR(x)B^R(x)BR(x) 的逆元，就可以得到 Q(x)Q(x)Q(x) ，代回去就可以得到 R(x)R(x)R(x) 。
时间复杂度 O(nlogn)O(n\log n)O(nlogn) 。
实现
模板题：https://www.luogu.org/problemnew/show/P4512
代码：
#include<bits/stdc++.h> using namespace std; typedef long long s64; #define rep(i,l,r) for(int i=l;i<=r;++i) #define gc (c=getchar()) int read() { char c; while(gc<'0'); int x=c-'0'; while(gc>='0')x=x*10+c-'0'; return x; } const int N=1<<18,D=998244353; s64 mi(s64 x,int y=D-2,int p=D) { s64 ans=1; while(y) { if(y&1)ans=ans*x%p; x=x*x%p;y>>=1; } return ans; } s64 a[N],b[N],a1[N]; namespace NTT { s64 w[N]; int rev[N]; void ntt(s64 a[],int n,int flag) { rep(i,1,n-1)rev[i]=rev[i/2]/2+i%2*n/2; rep(i,0,n-1) if(i<rev[i])swap(a[i],a[rev[i]]); for(int i=1;i<n;i<<=1) { s64 wn=mi(3,(D-1)/(2*i)*flag+D-1); w[0]=1; rep(k,1,i-1)w[k]=w[k-1]*wn%D; for(int j=0;j<n;j+=i*2) { s64 *a1=a+j,*a2=a1+i; rep(k,0,i-1) { s64 x=a1[k],y=a2[k]*w[k]; a1[k]=(x+y)%D; a2[k]=(x-y)%D; } } } if(flag==-1) { s64 niv_n=mi(n); rep(i,0,n-1)a[i]=a[i]*niv_n%D; } } }; using NTT::ntt; struct Poly { vector<s64>a; void set(int n) { a.resize(n+1); } Poly (int n) { set(n); } int size()const { return int(a.size())-1; } s64& operator [](int i) { return a[i]; } const s64& operator [](int i)const { return a[i]; } }; Poly operator *(const Poly &A,const Poly &B) { int n=1; while(n<=A.size()+B.size())n*=2; rep(i,0,n-1)a[i]=b[i]=0; rep(i,0,A.size())a[i]=A[i]; rep(i,0,B.size())b[i]=B[i]; ntt(a,n,1);ntt(b,n,1); rep(i,0,n-1)a[i]=a[i]*b[i]%D; ntt(a,n,-1); Poly ans(A.size()+B.size()); rep(i,0,ans.size())ans[i]=a[i]; return ans; } Poly operator -(Poly A,const Poly &B) { if(A.size()<B.size())A.set(B.size()); rep(i,0,B.size())A[i]-=B[i]; return A; } Poly rev(const Poly &A) { Poly B=A; reverse(B.a.begin(),B.a.end()); return B; } Poly niv(const Poly &A,int n0) { int n=1;a1[0]=mi(A[0]); while(n<n0) { n*=2; rep(i,0,n*2-1)a[i]=b[i]=0; rep(i,0,min(n-1,A.size()))a[i]=A[i]; rep(i,0,n/2-1)b[i]=a1[i]; ntt(a,n*2,1);ntt(b,n*2,1); rep(i,0,n*2-1)a[i]=a[i]*b[i]%D*b[i]%D; ntt(a,n*2,-1); rep(i,0,n-1)a1[i]=(((i<n/2)?(2*a1[i]):0)-a[i])%D; } Poly ans(n0-1); rep(i,0,n0-1)ans[i]=a1[i]; return ans; } pair<Poly,Poly> div(const Poly &A,const Poly &B) { int n=A.size(),m=B.size(); Poly _A=rev(A),_B=niv(rev(B),n-m+1); _A.set(n-m); Poly Q=_A*_B; Q.set(n-m); Q=rev(Q); Poly R=A-Q*B; R.set(m-1); return {Q,R}; } int main() { int n,m; cin>>n>>m; Poly f(n),g(m); rep(i,0,n)f[i]=read(); rep(i,0,m)g[i]=read(); auto ans=div(f,g); rep(i,0,n-m)printf("%d%c",int((ans.first[i]+D)%D)," \n"[i==n-m]); rep(i,0,m-1)printf("%d%c",int((ans.second[i]+D)%D)," \n"[i==m-1]); }
应用
- 线性递推的优化
对于一个数列 a0⋯na_{0 \cdots n}a0⋯n ，已知数列 p1⋯mp_{1\cdots m}p1⋯m 是 aaa 的一个递推式，即对于任意 i≥mi \ge mi≥m ，有 $a_i=\sum_{j=1}^{m}p_ja_{i-j} $ 。现在已知 a0..m−1a_{0..m-1}a0..m−1 和 p1..mp_{1..m}p1..m ，如何快速求出 ana_nan ？
一个比较暴力的方法就是用矩阵乘法做到 O(m3logn)O(m^3\log n)O(m3logn) ，这里不再赘述。
对于一个多项式 f(x)=∑i=0tcixif(x)=\sum_{i=0}^tc_ix^if(x)=∑i=0tcixi ，我们定义 $G(f)=\sum_{i=0}^{t}c_ia_i $ ，即 fff 的系数序列和 aaa 的点积。
我们要求的 ana_nan 就是 G(xn)G(x^n)G(xn) 。
显然 GGG 满足 $G(f)\pm G(g)=G( f \pm g ) $ ( f,gf,gf,g 是任意多项式)。
由于 $a_i=\sum_{j=1}^{m}p_ja_{i-j} $ ，如果我们令 $P(x)=xm-\sum_{i=1}{m}p_ix^{m-i} $ ，则 G(P)=0G(P)=0G(P)=0 。
同样的，$G(Px),G(Px^2)\cdots=0 $ ，所以有 G(Pf)=0G(Pf)=0G(Pf)=0 ( fff 是任意一个多项式)。
那么， G(xn)G(x^n)G(xn) 就等于 G(xnmodP)G(x^n \bmod P )G(xnmodP) 。
利用快速幂+多项式取模，我们可以在 O(mlogmlogn)O(m \log m \log n)O(mlogmlogn) 的时间内计算 xnmodPx^n \bmod PxnmodP ，然后 O(m)O(m)O(m) 计算 G(xnmodP)G(x^n \bmod P)G(xnmodP) 。
模板题：https://www.codechef.com/problems/RNG
代码：https://www.codechef.com/viewsolution/22088187
- 多项式多点求值和多点插值
多点求值是给一个多项式 F(x)F(x)F(x) 和 nnn 个值 x1,x2⋯xnx_1,x_2 \cdots x_nx1,x2⋯xn ，要求求出 $F(x_1),F(x_2)\cdots F(x_n) $ ；多点插值是给出 nnn 个点 $(x_1,y_1),(x_2,y_2) \cdots(x_n,y_n) $ ，要求求出一个 n−1n-1n−1 次多项式 F(x)F(x)F(x) ，使得 F(xi)=yi(i=1⋯n)F(x_i)=y_i(i=1\cdots n)F(xi)=yi(i=1⋯n) 。
在 FFTFFTFFT 中由于带入的值的特殊性，可以在 O(nlogn)O(n \log n)O(nlogn) 的时间完成这两个问题。
而对于一般的情况，这两个问题都可以做到 O(nlog2n)O(n \log^2 n)O(nlog2n) 。
多点求值
注意到， F(xi)=F(x)mod(x−xi)F(x_i)=F(x) \bmod (x-x_i)F(xi)=F(x)mod(x−xi) 。
证明是显然的，设 F(x)=Q(x)(x−xi)+RF(x)=Q(x)(x-x_i)+RF(x)=Q(x)(x−xi)+R ， 则当 x=xix=x_ix=xi 时，有 F(xi)=RF(x_i)=RF(xi)=R 。
考虑分治。
假设现在要求解 [l,r][l,r][l,r] 。
令 <mstyle displaystyle="true" scriptlevel="0">mid=⌊l+r2⌋</mstyle>\displaystyle mid=\lfloor \frac{l+r}{2} \rfloormid=⌊2l+r⌋ 。
令 $L(x)=\prod_{i=l}^{mid} (x-x_i) $ ，
则对于 i∈[l,mid]i \in [l,mid]i∈[l,mid] ，$F(x) \bmod (x-x_i)=(F(x) \bmod L(x))\bmod (x-x_i) $ ，因此可以把 F(x)F(x)F(x) 变成 F(x)modL(x)F(x) \bmod L(x)F(x)modL(x) 然后递归处理 [l,mid][l,mid][l,mid] 。
[mid+1,r][mid+1,r][mid+1,r] 同理。
L(x)L(x)L(x) 只要分治 FFTFFTFFT 预处理就好了。
模板题：https://www.luogu.org/problemnew/show/P5050
代码：https://www.luogu.org/paste/t45c5qu0
多点插值
由拉格朗日插值得： <mstyle displaystyle="true" scriptlevel="0">F(x)=<munderover>∑i=1n</munderover><munder>∏j≠i</munder>(x−xj)<munder>∏j≠i</munder>(xi−xj)yi</mstyle>\displaystyle F(x)=\sum_{i=1}^{n} \frac{ \prod_{j \not= i}(x-x_j) }{ \prod_{ j \not= i }(x_i-x_j) } y_iF(x)=i=1∑n∏j=i(xi−xj)∏j=i(x−xj)yi 。
我们先考虑对于每个 iii 求出 $ \prod_{j \not= i} (x_i-x_j) $ 。
设 $ M(x)=\prod_{i=1}^{n}(x-x_i) $ ，那么我们就是要求 $ \displaystyle \frac{M(x)}{x-x_i} $ 在 xix_ixi 处的值。
由洛必达法则可得，这个值就是 M′(x)M'(x)M′(x) 在 xix_ixi 处的值。
那么我们先分治 FFTFFTFFT 求出 M′(x)M'(x)M′(x) ，然后多点求值即可。
将 <mstyle displaystyle="true" scriptlevel="0">yi<munder>∏j≠i</munder>(xi−xj)</mstyle>\displaystyle \frac{y_i}{ \prod_{j \not= i} (x_i-x_j) }∏j=i(xi−xj)yi 记作 $v_i $ ，则我们现在就是要要求 $\sum_{i=1}^{n}v_i\prod_{j \not= i}(x-x_j) $ ，这显然可以分治。
具体来说，假设现在要求解 [l,r][l,r][l,r] ，我们先递归 [l,mid][l,mid][l,mid] 和 [mid+1,r][mid+1,r][mid+1,r] ，对于 [l,mid][l,mid][l,mid] 我们求出多项式 $L_0(x)=\sum_{i=l}^{mid}v_i\prod_{j \not= i,j \in [l,mid]}(x-x_j) $ ，$L_1(x)=\prod_{i=l}^{mid}(x-x_i) $ ，类似的对于 [mid+1,r][mid+1,r][mid+1,r] 求出 R0(x),R1(x)R_0(x),R_1(x)R0(x),R1(x) ，记 [l,r][l,r][l,r] 的这两个多项式为 F0(x),F1(x)F_0(x),F_1(x)F0(x),F1(x) ，则 $F_0(x)=L_0(x)R_1(x)+L_1(x)R_0(x),F_1(x)=L_1(x)R_1(x) $ 。
模板题：https://www.luogu.org/problemnew/show/P5158
代码：https://www.luogu.org/paste/xc7tafub
题目
http://acm.hdu.edu.cn/showproblem.php?pid=3892
https://www.codechef.com/NOV18A/problems/CHEFEQUA
参考资料
http://blog.miskcoo.com/2015/05/polynomial-division
https://blog.csdn.net/Coldef/article/details/76020530
http://codeforces.com/blog/entry/61306
https://www.cnblogs.com/zzqsblog/p/7923192.html
https://blog.csdn.net/qq_39972971/article/details/80732541
京公网安备 11010502036488号