1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath>10 #include <queue>11 #include <stack>12 #include <map>13 #include <set>14 #define inf (1<<30)15 #define pi acos(-1)16 #define N (600010)17 #define il inline18 #define RG register19 #define ll long long20 #define C complex<double>21 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)22 23 using namespace std;24 25 int rev[N],n,m,lg;26 char sa[N],sb[N];27 C a[N],b[N];28 29 il int gi(){30     RG int x=0,q=1; RG char ch=getchar();31     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();32     if (ch==‘-‘) q=-1,ch=getchar();33     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();34     return q*x;35 }36 37 il void fft(C *a,int n,int f){38     for (RG int i=0;i<n;++i) if (i<rev[i]) swap(a[i],a[rev[i]]);39     for (RG int i=1;i<n;i<<=1){40     C wn(cos(pi/i),sin(f*pi/i)),x,y;41     for (RG int j=0;j<n;j+=(i<<1)){42         C w(1,0);43         for (RG int k=0;k<i;++k,w*=wn){44         x=a[j+k],y=w*a[j+k+i];45         a[j+k]=x+y,a[j+k+i]=x-y;46         }47     }48     }49 }50 51 il void work(){52     n=gi()+1,m=gi()+1; for (RG int i=0;i<n;++i) a[i]=gi();53     for (RG int i=0;i<m;++i) b[i]=gi(); m+=n; for (n=1;n<=m;n<<=1) lg++;54     for (RG int i=1;i<=n;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));55     fft(a,n,1),fft(b,n,1); for (RG int i=0;i<n;++i) a[i]*=b[i]; fft(a,n,-1);56     for (RG int i=0;i<m-1;++i) printf("%d ",(int)(a[i].real()/n+0.5)); return;57 }58 59 int main(){60     File("fft");61     work();62     return 0;63 }

 1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath>10 #include <queue>11 #include <stack>12 #include <map>13 #include <set>14 #define rhl (998244353)15 #define inf (1<<30)16 #define N (300010)17 #define G (3)18 #define il inline19 #define RG register20 #define ll long long21 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)22 23 using namespace std;24 25 int rev[N],n,m,lg;26 ll a[N],b[N];27 28 il int gi(){29     RG int x=0,q=1; RG char ch=getchar();30     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();31     if (ch==‘-‘) q=-1,ch=getchar();32     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();33     return q*x;34 }35 36 il ll qpow(RG ll a,RG ll b){37     RG ll ans=1;38     while (b){39     if (b&1) (ans*=a)%=rhl;40     (a*=a)%=rhl,b>>=1;41     }42     return ans;43 }44 45 il void NTT(ll *a,RG int n,RG int f){46     for (RG int i=0;i<n;++i) if (i<rev[i]) swap(a[i],a[rev[i]]);47     for (RG int i=1;i<n;i<<=1){48     RG ll gn=qpow(G,(rhl-1)/(i<<1)),x,y;49     for (RG int j=0;j<n;j+=(i<<1)){50         RG ll g=1;51         for (RG int k=0;k<i;++k,(g*=gn)%=rhl){52         x=a[j+k],y=g*a[j+k+i]%rhl;53         a[j+k]=(x+y)%rhl,a[j+k+i]=(x-y+rhl)%rhl;54         }55     }56     }57     if (f==1) return; reverse(a+1,a+n); RG ll inv=qpow(n,rhl-2);58     for (RG int i=0;i<n;++i) (a[i]*=inv)%=rhl; return;59 }60 61 il void work(){62     n=gi()+1,m=gi()+1;63     for (RG int i=0;i<n;++i) a[i]=gi();64     for (RG int i=0;i<m;++i) b[i]=gi();65     m+=n; for (n=1;n<=m;n<<=1) lg++;66     for (RG int i=0;i<n;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));67     NTT(a,n,1),NTT(b,n,1); for (RG int i=0;i<n;++i) (a[i]*=b[i])%=rhl;68     NTT(a,n,-1); for (RG int i=0;i<m-1;++i) printf("%lld ",a[i]); return;69 }70 71 int main(){72     File("NTT");73     work();74     return 0;75 }