UOJ#34. 多项式乘法

//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1<<30)
#define pi acos(-1)
#define N (600010)
#define il inline
#define RG register
#define ll long long
#define C complex<double>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

using namespace std;

int rev[N],n,m,lg;
char sa[N],sb[N];
C a[N],b[N];

il int gi(){
    RG int x=0,q=1; RG char ch=getchar(); while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();
    if (ch==‘-‘) q=-1,ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); return q*x;
}

il void fft(C *a,int n,int f){
    for (RG int i=0;i<n;++i) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (RG int i=1;i<n;i<<=1){
    C wn(cos(pi/i),sin(f*pi/i)),x,y;
    for (RG int j=0;j<n;j+=(i<<1)){
        C w(1,0);
        for (RG int k=0;k<i;++k,w*=wn){
        x=a[j+k],y=w*a[j+k+i];
        a[j+k]=x+y,a[j+k+i]=x-y;
        }
    }
    }
}

il void work(){
    n=gi()+1,m=gi()+1; for (RG int i=0;i<n;++i) a[i]=gi();
    for (RG int i=0;i<m;++i) b[i]=gi(); m+=n; for (n=1;n<=m;n<<=1) lg++;
    for (RG int i=1;i<=n;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
    fft(a,n,1),fft(b,n,1); for (RG int i=0;i<n;++i) a[i]*=b[i]; fft(a,n,-1);
    for (RG int i=0;i<m-1;++i) printf("%d ",(int)(a[i].real()/n+0.5)); return;
}

int main(){
    File("fft");
    work();
    return 0;
}