求助 拆系数FFT

#include<bits/stdc++.h>

using namespace std;

#define il inline void
#define ll long long
#define inf 0x3f3f3f3f
#define maxx(a,b) (a>b?a:b)
#define minn(a,b) (a<b?a:b)
#define reg register
#define pii pair<int,int>
#define x first
#define y second

#define mp make_pair
#define pb push_back
#define mcp(n,x) memcpy(n,x,sizeof(x))
#define itn int
#define cosnt const
#define mem(n,x) memset(n,x,sizeof(n))
struct control{
    int ct,val;
    control(int Ct,int Val=-1):ct(Ct),val(Val){}
    inline control operator()(int Val){
        return control(ct,Val);
    }
}_endl(0),_prs(1),_setprecision(2);
struct FastIO{
    #define IOSIZE 10000000
    char in[IOSIZE],*p,*pp,out[IOSIZE],*q,*qq,ch[20],*t,b,K,prs;
    FastIO():p(in),pp(in),q(out),qq(out+IOSIZE),t(ch),b(1),K(6){}
    ~FastIO(){fwrite(out,1,q-out,stdout);}
    inline char getch(){
        return p==pp&&(pp=(p=in)+fread(in,1,IOSIZE,stdin),p==pp)?b=0,EOF:*p++;
    }
    inline void putch(char x){
        q==qq&&(fwrite(out,1,q-out,stdout),q=out),*q++=x;
    }
    inline void puts(const char str[]){fwrite(out,1,q-out,stdout),fwrite(str,1,strlen(str),stdout),q=out;}
    inline void getline(string& s){
        s="";
        for(reg char ch;(ch=getch())!='\n'&&b;)s+=ch;
    }
    #define indef(T) inline FastIO& operator>>(T& x){\
        x=0;reg char f=0,ch;\
        while(!isdigit(ch=getch())&&b)f|=ch=='-';\
        while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getch();\
        return x=f?-x:x,*this;\
    }
    indef(int)
    indef(long long)
    inline FastIO& operator>>(char& ch){return ch=getch(),*this;}
    inline FastIO& operator>>(string& s){
        s="";reg char ch;
        while(isspace(ch=getch())&&b);
        while(!isspace(ch)&&b)s+=ch,ch=getch();
        return *this;
    }
    inline FastIO& operator>>(double& x){
        x=0;reg char f=0,ch;
        double d=0.1;
        while(!isdigit(ch=getch())&&b)f|=(ch=='-');
        while(isdigit(ch))x=x*10+(ch^48),ch=getch();
        if(ch=='.')while(isdigit(ch=getch()))x+=d*(ch^48),d*=0.1;
        return x=f?-x:x,*this;
    }
    #define outdef(_T) inline FastIO& operator<<(_T x){\
        !x&&(putch('0'),0),x<0&&(putch('-'),x=-x);\
        while(x)*t++=x%10+48,x/=10;\
        while(t!=ch)*q++=*--t;\
        return *this;\
    }
    outdef(int)
    outdef(long long)
    inline FastIO& operator<<(char ch){return putch(ch),*this;}
    inline FastIO& operator<<(const char str[]){return puts(str),*this;}
    inline FastIO& operator<<(const string& s){return puts(s.c_str()),*this;}
    inline FastIO& operator<<(double x){
        reg int k=0;
        this->operator<<(int(x));
        putch('.');
        x-=int(x);
        prs&&(x+=5*pow(10,-K-1));
        while(k<K)putch(int(x*=10)^48),x-=int(x),++k;
        return *this;
    }
    inline FastIO& operator<<(const control& cl){
        switch(cl.ct){
            case 0:putch('\n');break;
            case 1:prs=cl.val;break;
            case 2:K=cl.val;break;
        }
    }
    inline operator bool(){return b;}
}io;
#define int ll
const double Pi=acos(-1);
const int N=3000005;
struct Complex{
    double x,y;
    Complex operator +(const Complex& t) const
    {
        return {x+t.x,y+t.y};
    }
    Complex operator -(const Complex& t) const
    {
        return {x-t.x,y-t.y};
    }
    Complex operator *(const Complex& t) const
    {
        return {x*t.x-y*t.y,x*t.y+y*t.x};
    }   
    Complex operator /(const double& t) const
    {
        return {x/t,y/t};
    }
    Complex operator *(const double& t) const
    {
        return {x*t,y*t};
    }
    Complex conj()
    {
        return {x,-y};
    }
}a0[N],b0[N],a1[N],b1[N],p[N],q[N];
Complex I={0,1};
int n,m,mod;
int rev[N],bit,tot;
ll num(double x)
{
    return x<0?(ll)(x-0.5)%mod:(ll)(x+0.5)%mod;
}
void fft(Complex a[],int inv)
{
    for(int i=0;i<tot;++i)
    if(i<rev[i])
    swap(a[rev[i]],a[i]);
    for(int mid=1;mid<tot;mid<<=1)
    {
        auto w1=Complex{cos(Pi/mid),inv*sin(Pi/mid)};
        for(int i=0;i<tot;i+=mid*2)
        {
            auto wk=Complex{1,0};
            for(int j=0;j<mid;j++,wk=wk*w1)
            {
                auto x=a[i+j],y=wk*a[i+j+mid];
                a[i+j]=x+y,a[i+j+mid]=x-y;
            }
        }
    }
    if(inv==-1)
    {
        for(int i=0;i<tot;++i)
        a[i]=a[i]/tot;
    }
}
void fft2(Complex a[],Complex b[],int inv)
{
    for(int i=0;i<tot;++i) a[i]=a[i]+I*b[i];
    fft(a,inv);
    for(int i=0;i<tot;++i) b[i]=a[i?tot-i:0].conj();
    for(int i=0;i<tot;++i)
    {
        auto x=a[i],y=b[i];
        a[i]=(x+y)*0.5;
        b[i]=(x-y)*0.5*I;
    }
} 

signed main()
{
    #ifdef CHECK
    freopen("test.txt","r",stdin);
    freopen("rua.txt","w",stdout);
    double times=clock();
    #endif
    #ifndef ONLINE_JUDGE
    #ifndef CHECK
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    #endif
    #endif
    io>>n>>m>>mod;
    int temp;
    for(int i=0;i<=n;++i)
    {

        io>>temp;
        temp%=mod;
        a0[i].x=temp>>15;
        a1[i].x=temp&0x7fff;
    }
    for(int i=0;i<=m;++i)
    {
        io>>temp;
        temp%=mod;
        b0[i].x=temp>>15;
        b1[i].x=temp&0x7fff;
    }

    while((1<<bit)<=n+m)
    bit++;
    tot=1<<bit;
    for(int i=0;i<tot;++i)
    rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));

    fft2(a0,a1,1);
    fft2(b0,b1,1);

    for(int i=0;i<tot;++i)
    {
        p[i]=a0[i]*b0[i]+I*a1[i]*b0[i];
        q[i]=a0[i]*b1[i]+I*a1[i]*b1[i];
    }

    fft(p,-1);
    fft(q,-1);

    for(int i=0;i<=n+m;++i)
    {
        printf("%lld ",(((num(p[i].x)<<30ll)%mod+(num(p[i].y)<<15ll)%mod+(num(q[i].x)<<15ll)%mod+(num(q[i].y))%mod)%mod+mod)%mod);
    }
    #ifdef CHECK
    printf("%lf\n",(clock()-times)/1000);
    #endif
    return 0;
}