【模板】多项式除法

传送门:洛谷：【模板】多项式除法

题意

给定一个 n n $n$ 次多项式 F(x)" role="presentation" style="position: relative;">F(x)F(x)$F(x)$ 和一个 m m $m$ 次多项式 G(x)" role="presentation" style="position: relative;">G(x)G(x)$G(x)$ ，请求出多项式 Q(x) Q ( x ) $Q(x)$ , R(x) R ( x ) $R(x)$ ，满足以下条件：
Q(x) Q ( x ) $Q(x)$ 次数为 n−m n − m $n-m$， R(x) R ( x ) $R(x)$ 次数小于 m m $m$
F(x)=Q(x)×G(x)+R(x)" role="presentation" style="position: relative;">F(x)=Q(x)×G(x)+R(x)F(x)=Q(x)×G(x)+R(x)$F(x) = Q(x) \times G(x) + R(x)$
所有的运算在模 998244353 998244353 $998244353$ 意义下进行。

题解

由 F(x)=Q(x)×G(x)+R(x) (mod xn+1) F ( x ) = Q ( x ) × G ( x ) + R ( x ) ( m o d x n + 1 ) $F(x)=Q(x)\times G(x)+R(x)\ (mod \ x^{n+1})$
得 F(1x)=Q(1x)×G(1x)+R(1x) (mod xn+1) F ( 1 x ) = Q ( 1 x ) × G ( 1 x ) + R ( 1 x ) ( m o d x n + 1 ) $F(\frac{1}{x})=Q(\frac{1}{x})\times G(\frac{1}{x})+R(\frac{1}{x}) \ (mod\ x^{n+1})$
同乘上一个 xn x n $x^n$即 Frev(x)=Qrev(x)×Grev(x)+Rrev(x)xn−degR (mod xn+1) F r e v ( x ) = Q r e v ( x ) × G r e v ( x ) + R r e v ( x ) x n − d e g R ( m o d x n + 1 ) $F^{rev}(x)=Q^{rev}(x)\times G^{rev}(x)+R^{rev}(x)x^{n-degR} \ (mod\ x^{n+1})$
其中 Frev(x) F r e v ( x ) $F^{rev}(x)$表示将多项式 F(x) F ( x ) $F(x)$的 0,1...n 0 , 1... n $0,1...n$次项的系数翻转。 degR d e g R $degR$表示 R R $R$的次数。
因为degR&lt;m" role="presentation" style="position: relative;">degR<mdegR<m$degR<m$，显然 n−degR>n−m n − d e g R > n − m $n-degR>n-m$。而 degQ=n−m d e g Q = n − m $degQ=n-m$
那么在 mod n−m+1 m o d n − m + 1 $mod \ n-m+1$意义下，存在：
Frev(x)=Qrev(x)×Grev(x) (mod xn−m+1) F r e v ( x ) = Q r e v ( x ) × G r e v ( x ) ( m o d x n − m + 1 ) $F^{rev}(x)=Q^{rev}(x)\times G^{rev}(x) \ (mod\ x^{n-m+1})$
Rrev R r e v $R^{rev}$既然已被消去，那么只需要一个多项式求逆即可得出 Qrev(x) Q r e v ( x ) $Q^{rev}(x)$，在翻转回去就是答案，而 degQ<n−m+1 d e g Q < n − m + 1 $degQ<n-m+1$，所以答案满足条件，成立。
得出 Q(x) Q ( x ) $Q(x)$后，直接带回在 (mod xn+1) ( m o d x n + 1 ) $(mod\ x^{n+1})$意义下做个多项式乘法，用 F(x) F ( x ) $F(x)$减去就是 R(x) R ( x ) $R(x)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,g=3;
const int N=3e5+1000;
int n,m,rvg,a[N],b[N],c[N],d[N],rv[N],ans[N];inline int ad(int x,int y) {x+=y;if(x>=mod) x-=mod;return x;}
inline int dc(int x,int y) {x-=y;if(x<0) x+=mod;return x;}
inline int mul(int x,int y) {return 1ll*x*y%mod;}template<class T>
inline void rd(T &x)
{char c=getchar();int f=0;x=0;while(!isdigit(c)) {if(c=='-') f=1;c=getchar();}while(isdigit(c)) {x=x*10+(c^48);c=getchar();}if(f) x=-x;
}inline int fp(int x,int y)
{int re=1;for(;y;y>>=1,x=mul(x,x))if(y&1) re=mul(re,x);return re;
}inline void NTT(int *e,int ptr,int n)
{int i,j,k,ori,pd,ix,iy,G;G= ptr?g:rvg;for(i=0;i<n;++i) if(i<rv[i]) swap(e[i],e[rv[i]]);for(i=1;i<n;i<<=1){ori=fp(G,(mod-1)/(i<<1));for(j=0;j<n;j+=(i<<1)){pd=1;for(k=0;k<i;++k,pd=mul(pd,ori)){ix=e[j+k];iy=mul(e[i+j+k],pd);e[j+k]=ad(ix,iy);e[i+j+k]=dc(ix,iy);}}}if(ptr) return;G=fp(n,mod-2);for(i=0;i<n;++i) e[i]=mul(e[i],G);
}inline void getinv(int n,int *a,int *b)
{if(n==1) {b[0]=fp(a[0],mod-2);return;}getinv((n+1)>>1,a,b);int i,j,L=0,len=1;for(;len<n+n;len<<=1) L++;for(i=1;i<len;++i) rv[i]=((rv[i>>1]>>1)|((i&1)<<(L-1)));for(i=0;i<n;++i) d[i]=a[i];for(i=n;i<len;++i) d[i]=0;NTT(b,1,len);NTT(d,1,len);for(i=0;i<len;++i) b[i]=mul(b[i],dc(2,mul(b[i],d[i])));NTT(b,0,len);for(i=n;i<len;++i) b[i]=0;
}inline void getmul(int *a,int *b,int *c,int n,int m)
{int i,j,len=1,L=0;for(;len<n+m;len<<=1) L++;for(i=1;i<len;++i) rv[i]=((rv[i>>1]>>1)|((i&1)<<(L-1)));static int u[N],k[N];for(i=0;i<n;++i) u[i]=a[i];for(i=n;i<len;++i) u[i]=0;for(i=0;i<m;++i) k[i]=b[i];for(i=m;i<len;++i) k[i]=0;NTT(u,1,len);NTT(k,1,len);for(i=0;i<len;++i) c[i]=mul(u[i],k[i]);NTT(c,0,len);
}int main(){int i,j;rd(n);rd(m);rvg=fp(g,mod-2);for(i=n;i>=0;--i) rd(a[i]);for(i=m;i>=0;--i) rd(b[i]);n++;m++;getinv(n-m+1,b,c);getmul(a,c,d,n,n-m+1);reverse(d,d+n-m+1);for(i=0;i<=n-m;++i) ans[i]=d[i],printf("%d ",ans[i]);reverse(a,a+n);reverse(b,b+m);puts(""); getmul(b,ans,c,m,n-m+1);for(i=0;i<m-1;++i) printf("%d ",dc(a[i],c[i]));
}

【模板】多项式除法

传送门:洛谷：【模板】多项式除法

题意

给定一个 n n $n$ 次多项式 F(x)" role="presentation" style="position: relative;">F(x)F(x)$F(x)$ 和一个 m m $m$ 次多项式 G(x)" role="presentation" style="position: relative;">G(x)G(x)$G(x)$ ，请求出多项式 Q(x) Q ( x ) $Q(x)$ , R(x) R ( x ) $R(x)$ ，满足以下条件：
Q(x) Q ( x ) $Q(x)$ 次数为 n−m n − m $n-m$， R(x) R ( x ) $R(x)$ 次数小于 m m $m$
F(x)=Q(x)&#x00D7;G(x)+R(x)" role="presentation" style="position: relative;">F(x)=Q(x)×G(x)+R(x)F(x)=Q(x)×G(x)+R(x)$F(x) = Q(x) \times G(x) + R(x)$
所有的运算在模 998244353 998244353 $998244353$ 意义下进行。

题解

由 F(x)=Q(x)×G(x)+R(x) (mod xn+1) F ( x ) = Q ( x ) × G ( x ) + R ( x ) ( m o d x n + 1 ) $F(x)=Q(x)\times G(x)+R(x)\ (mod \ x^{n+1})$
得 F(1x)=Q(1x)×G(1x)+R(1x) (mod xn+1) F ( 1 x ) = Q ( 1 x ) × G ( 1 x ) + R ( 1 x ) ( m o d x n + 1 ) $F(\frac{1}{x})=Q(\frac{1}{x})\times G(\frac{1}{x})+R(\frac{1}{x}) \ (mod\ x^{n+1})$
同乘上一个 xn x n $x^n$即 Frev(x)=Qrev(x)×Grev(x)+Rrev(x)xn−degR (mod xn+1) F r e v ( x ) = Q r e v ( x ) × G r e v ( x ) + R r e v ( x ) x n − d e g R ( m o d x n + 1 ) $F^{rev}(x)=Q^{rev}(x)\times G^{rev}(x)+R^{rev}(x)x^{n-degR} \ (mod\ x^{n+1})$
其中 Frev(x) F r e v ( x ) $F^{rev}(x)$表示将多项式 F(x) F ( x ) $F(x)$的 0,1...n 0 , 1... n $0,1...n$次项的系数翻转。 degR d e g R $degR$表示 R R $R$的次数。
因为degR&lt;m" role="presentation" style="position: relative;">degR<mdegR<m$degR<m$，显然 n−degR>n−m n − d e g R > n − m $n-degR>n-m$。而 degQ=n−m d e g Q = n − m $degQ=n-m$
那么在 mod n−m+1 m o d n − m + 1 $mod \ n-m+1$意义下，存在：
Frev(x)=Qrev(x)×Grev(x) (mod xn−m+1) F r e v ( x ) = Q r e v ( x ) × G r e v ( x ) ( m o d x n − m + 1 ) $F^{rev}(x)=Q^{rev}(x)\times G^{rev}(x) \ (mod\ x^{n-m+1})$
Rrev R r e v $R^{rev}$既然已被消去，那么只需要一个多项式求逆即可得出 Qrev(x) Q r e v ( x ) $Q^{rev}(x)$，在翻转回去就是答案，而 degQ<n−m+1 d e g Q < n − m + 1 $degQ<n-m+1$，所以答案满足条件，成立。
得出 Q(x) Q ( x ) $Q(x)$后，直接带回在 (mod xn+1) ( m o d x n + 1 ) $(mod\ x^{n+1})$意义下做个多项式乘法，用 F(x) F ( x ) $F(x)$减去就是 R(x) R ( x ) $R(x)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,g=3;
const int N=3e5+1000;
int n,m,rvg,a[N],b[N],c[N],d[N],rv[N],ans[N];inline int ad(int x,int y) {x+=y;if(x>=mod) x-=mod;return x;}
inline int dc(int x,int y) {x-=y;if(x<0) x+=mod;return x;}
inline int mul(int x,int y) {return 1ll*x*y%mod;}template<class T>
inline void rd(T &x)
{char c=getchar();int f=0;x=0;while(!isdigit(c)) {if(c=='-') f=1;c=getchar();}while(isdigit(c)) {x=x*10+(c^48);c=getchar();}if(f) x=-x;
}inline int fp(int x,int y)
{int re=1;for(;y;y>>=1,x=mul(x,x))if(y&1) re=mul(re,x);return re;
}inline void NTT(int *e,int ptr,int n)
{int i,j,k,ori,pd,ix,iy,G;G= ptr?g:rvg;for(i=0;i<n;++i) if(i<rv[i]) swap(e[i],e[rv[i]]);for(i=1;i<n;i<<=1){ori=fp(G,(mod-1)/(i<<1));for(j=0;j<n;j+=(i<<1)){pd=1;for(k=0;k<i;++k,pd=mul(pd,ori)){ix=e[j+k];iy=mul(e[i+j+k],pd);e[j+k]=ad(ix,iy);e[i+j+k]=dc(ix,iy);}}}if(ptr) return;G=fp(n,mod-2);for(i=0;i<n;++i) e[i]=mul(e[i],G);
}inline void getinv(int n,int *a,int *b)
{if(n==1) {b[0]=fp(a[0],mod-2);return;}getinv((n+1)>>1,a,b);int i,j,L=0,len=1;for(;len<n+n;len<<=1) L++;for(i=1;i<len;++i) rv[i]=((rv[i>>1]>>1)|((i&1)<<(L-1)));for(i=0;i<n;++i) d[i]=a[i];for(i=n;i<len;++i) d[i]=0;NTT(b,1,len);NTT(d,1,len);for(i=0;i<len;++i) b[i]=mul(b[i],dc(2,mul(b[i],d[i])));NTT(b,0,len);for(i=n;i<len;++i) b[i]=0;
}inline void getmul(int *a,int *b,int *c,int n,int m)
{int i,j,len=1,L=0;for(;len<n+m;len<<=1) L++;for(i=1;i<len;++i) rv[i]=((rv[i>>1]>>1)|((i&1)<<(L-1)));static int u[N],k[N];for(i=0;i<n;++i) u[i]=a[i];for(i=n;i<len;++i) u[i]=0;for(i=0;i<m;++i) k[i]=b[i];for(i=m;i<len;++i) k[i]=0;NTT(u,1,len);NTT(k,1,len);for(i=0;i<len;++i) c[i]=mul(u[i],k[i]);NTT(c,0,len);
}int main(){int i,j;rd(n);rd(m);rvg=fp(g,mod-2);for(i=n;i>=0;--i) rd(a[i]);for(i=m;i>=0;--i) rd(b[i]);n++;m++;getinv(n-m+1,b,c);getmul(a,c,d,n,n-m+1);reverse(d,d+n-m+1);for(i=0;i<=n-m;++i) ans[i]=d[i],printf("%d ",ans[i]);reverse(a,a+n);reverse(b,b+m);puts(""); getmul(b,ans,c,m,n-m+1);for(i=0;i<m-1;++i) printf("%d ",dc(a[i],c[i]));
}