当前位置：首页 > news >正文

P4512 【模板】多项式除法

news 2026/3/27 10:24:23

P4512 【模板】多项式除法

题目描述

给定一个n nn次多项式F ( x ) F(x)F(x)和一个m mm次多项式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-mn−m，R ( x ) R(x)R(x)次数小于m mm
F ( x ) = Q ( x ) ∗ G ( x ) + R ( x ) F(x) = Q(x) * G(x) + R(x)F(x)=Q(x)∗G(x)+R(x)

所有的运算在模998244353 998244353998244353意义下进行。

输入格式

第一行两个整数n nn，m mm，意义如上。
第二行n + 1 n+1n+1个整数，从低到高表示F ( x ) F(x)F(x)的各个系数。
第三行m + 1 m+1m+1个整数，从低到高表示G ( x ) G(x)G(x)的各个系数。

输出格式

第一行n − m + 1 n-m+1n−m+1个整数，从低到高表示Q ( x ) Q(x)Q(x)的各个系数。
第二行m mm个整数，从低到高表示R ( x ) R(x)R(x)的各个系数。
如果R ( x ) R(x)R(x)不足m − 1 m-1m−1次，多余的项系数补0 00。

输入输出样例 #1

输入 #1

5 1 1 9 2 6 0 8 1 7

输出 #1

237340659 335104102 649004347 448191342 855638018 760903695

说明/提示

对于所有数据，1 ≤ m < n ≤ 10 5 1 \le m < n \le 10^51≤m<n≤105，给出的系数均属于[ 0 , 998244353 ) ∩ Z [0, 998244353) \cap \mathbb{Z}[0,998244353)∩Z。

思路

直接NTT即可。

代码

#include<bits/stdc++.h>usingnamespacestd;longlongn,m,nn=1,nn2=1,uv[4000006][2];constlonglongmod=998244353;longlonga[4000006],b[4000006],c[4000006],d[4000006],f[4000006],g[2000006],g2[2000006];longlongpow2(longlonga1,longlongb1){longlongc1=1;while(b1!=0){if(b1%2==1){c1=c1*a1%mod;}a1=a1*a1%mod;b1/=2;}returnc1;}voidntt(longlongn1,longlong*a1,longlongb1){if(n1<=1){return;}longlongax[n1/2],ay[n1/2];for(inti=0;i<=n1-1;i+=2){ax[i/2]=a1[i];ay[i/2]=a1[i+1];}ntt(n1/2,ax,b1);ntt(n1/2,ay,b1);longlongww,w=1;if(b1==1){if(uv[n1][0]==0){ww=pow2(3ll,(mod-1)*pow2(n1,mod-2)%mod);uv[n1][0]=pow2(3ll,(mod-1)*pow2(n1,mod-2)%mod);}else{ww=uv[n1][0];}}else{if(uv[n1][1]==0){ww=pow2(pow2(3ll,(mod-1)*pow2(n1,mod-2)%mod),mod-2);uv[n1][1]=pow2(pow2(3ll,(mod-1)*pow2(n1,mod-2)%mod),mod-2);}else{ww=uv[n1][1];}}for(inti=0;i<=n1/2-1;i++,w=w*ww%mod){a1[i]=(ax[i]+w*ay[i])%mod;a1[i+n1/2]=(ax[i]-w*ay[i]%mod+mod)%mod;}return;}intmain(){cin>>n>>m;for(inti=0;i<=n;i++){cin>>f[i];}for(inti=0;i<=m;i++){cin>>g[i];g2[i]=g[i];}for(inti=0;i<=n/2;i++){swap(f[i],f[n-i]);}for(inti=0;i<=m/2;i++){swap(g[i],g[m-i]);}for(inti=n-m+1;i<=m;i++){g[i]=0;}a[0]=pow2(g[0],mod-2);while(nn<=n-m+1+n-m+1){nn*=2;nn2=pow2(nn*2ll%mod,mod-2);for(inti=0;i<=nn-1;i++){c[i]=b[i]=0;}for(inti=0;i<=nn/2-1;i++){c[i]=a[i];}ntt(nn*2,a,1);for(inti=0;i<=nn-1;i++){b[i]=g[i];}ntt(nn*2,b,1);for(inti=0;i<=nn*2-1;i++){a[i]=a[i]*b[i]%mod;}ntt(nn*2,a,-1);for(inti=0;i<=nn*2-1;i++){a[i]=a[i]*nn2%mod;a[i]=mod-a[i];}a[0]=(a[0]+2ll)%mod;ntt(nn*2,a,1);ntt(nn*2,c,1);for(inti=0;i<=nn*2-1;i++){a[i]=a[i]*c[i]%mod;}ntt(nn*2,a,-1);for(inti=0;i<=nn*2-1;i++){a[i]=a[i]*nn2%mod;if(i>=nn){a[i]=0;}}}nn=1;while(nn<=n+n){nn*=2;}nn2=pow2(nn,mod-2);for(inti=n-m+1;i<=nn-1;i++){a[i]=0;}ntt(nn,a,1);for(inti=0;i<=nn-1;i++){b[i]=f[i];}ntt(nn,b,1);for(inti=0;i<=nn;i++){a[i]=a[i]*b[i]%mod;}ntt(nn,a,-1);for(inti=0;i<=nn-1;i++){a[i]=a[i]*nn2%mod;if(i>=n-m+1){a[i]=0;}}for(inti=0;i<=(n-m)/2;i++){swap(a[i],a[n-m-i]);//cout<<a[i]<<" ";}for(inti=0;i<=n-m;i++){//swap(a[i],a[n-m-i]);cout<<a[i]<<" ";}cout<<endl;for(inti=0;i<=m;i++){g[i]=g2[i];}for(inti=0;i<=n/2;i++){swap(f[i],f[n-i]);}nn=1;while(nn<=n+n){nn*=2;}nn2=pow2(nn,mod-2);for(inti=0;i<=nn-1;i++){b[i]=c[i]=0;}for(inti=0;i<=n-m;i++){c[i]=a[i];}ntt(nn,c,1);for(inti=0;i<=m;i++){b[i]=g[i];}ntt(nn,b,1);for(inti=0;i<=nn;i++){c[i]=c[i]*b[i]%mod;}ntt(nn,c,-1);for(inti=0;i<=nn-1;i++){c[i]=c[i]*nn2%mod;}for(inti=0;i<=n;i++){c[i]=(f[i]-c[i]+mod)%mod;}for(inti=0;i<=m-1;i++){cout<<c[i]<<" ";}cout<<endl;return0;}