FFT修正

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('
')
using namespace std;
const int maxm=300000+10,maxn=100000+10;
const double pi=acos(-1.0);
struct fft{
    struct cx{
        double r,i;cx(double _r=0.0,double _i=0.0){r=_r;i=_i;}
        cx operator+(const cx&a){return cx(r+a.r,i+a.i);}
        cx operator-(const cx&a){return cx(r-a.r,i-a.i);}
        cx operator*(const cx&a){return cx(r*a.r-i*a.i,r*a.i+i*a.r);}
    }f[maxm];int len;
    void init(int*s,int L,int len){
        this->len=len;for(int i=0;i<L;i++)f[i]=cx(s[L-i-1],0.0);return;
    }
    void change(){
        for(int i=1,j=len>>1;i<len-1;i++){
            if(i<j)swap(f[i],f[j]);int k=len>>1;
            while(j>=k)j-=k,k>>=1;if(j<k)j+=k;
        } return;
    }
    void cal(int tp){
        change();double tm=-tp*2*pi;
        for(int i=2;i<=len;i<<=1){
            double tr=tm/i;cx wn(cos(tr),sin(tr));
            for(int j=0;j<len;j+=i){
                cx w(1,0);int tn=i>>1;
                for(int k=j;k<j+tn;k++){
                    cx u=f[k],t=w*f[k+tn];
                    f[k]=u+t;f[k+tn]=u-t;w=w*wn;
                }
            }
        }if(tp<0) for(int i=0;i<len;i++) f[i].r/=len;return;
    }
};
void mul(int*s,int*t,int L1,int L2,int&L,int*ans){
    L=1;while(L<L1<<1||L<L2<<1)L<<=1;static fft a,b;
    a.init(s,L1,L);b.init(t,L2,L);a.cal(1);b.cal(1);
    for(int i=0;i<L;i++) a.f[i]=a.f[i]*b.f[i];a.cal(-1);
    for(int i=0;i<L;i++) ans[i]=(int)(a.f[i].r+0.5);return;
}
inline int read(){
    int x=0,sig=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
    while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
    return x*sig;
}
inline void write(int x){
    if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x;
    int len=0,buf[15];while(x) buf[len++]=x%10,x/=10;
    for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
}
int s[maxn],t[maxn],ans[maxm],L1,L2,L;
void init(){
    L1=read()+1;L2=read()+1;
    for(int i=0;i<L1;i++) s[i]=read();
    for(int i=0;i<L2;i++) t[i]=read();
    mul(s,t,L1,L2,L,ans);
    return;
}
void work(){
    int lim=L1+L2-2;
    for(L--;!ans[L]&&L&&L>lim;L--);
    for(int i=L;i>=0;i--) write(ans[i]),PAU;
    return;
}
void print(){
    return;
}
int main(){init();work();print();return 0;}