代码

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=3e6+50;
const double pi=acos(-1);
int n,m,r[N],lo[N];
struct cp{
    double x,y;
    // cp(double x=0,double y=0):x(x),y(y){}
    cp operator +(const cp &b){return (cp){x+b.x,y+b.y};}
    cp operator -(const cp &b){return (cp){x-b.x,y-b.y};}
    cp operator *(const cp &b){return (cp){x*b.x-y*b.y,x*b.y+y*b.x};}
    cp operator ~(){return (cp){x,-y};}
}rt[N],irt[N];
#define vec vector<cp>
int Glim(int n){int t=1;while(t<n)t<<=1;return t;}
void init(int n){
    // while(lim<n)lim<<=1,l++;
    int lim=Glim(n);
    for(int i=2,j=0;i<=lim;i<<=1,j++)lo[i]=j;
    rt[lim>>1]=(cp){1,0};cp w=(cp){cos(2*pi/lim),sin(2*pi/lim)};
    for(int i=(lim>>1)+1;i<lim;i++)rt[i]=rt[i-1]*w;
    for(int i=(lim>>1)-1;i;i--)rt[i]=rt[i<<1];
    for(int i=1;i<lim;i++)irt[i]=~rt[i];
}
void FFT(vec &a,cp *w,int lim){
    a.resize(lim);
    for(int i=0;i<lim;i++)r[i]=r[i>>1]>>1^(i&1)<<lo[lim];
    for(int i=0;i<lim;i++)if(i<r[i])swap(a[i],a[r[i]]);
    for(int i=1;i<lim;i<<=1){
        for(int t=i<<1,j=0;j<lim;j+=t){
            for(int k=0;k<i;k++){
                cp x=a[j+k],y=a[i+j+k]*w[i|k];
                a[j+k]=x+y;a[i+j+k]=x-y;
            }
        }
    }
}
vec operator *(vec a,vec b){
    // int n=a.size()+b.size()-1,lim=Glim(n);
    // dft(a,lim);dft(b,lim);
    // for(int i=0;i<lim;i++)a[i]=a[i]*b[i];
    // idft(a,lim);a.resize(n);return a;
    vec P,Q,A,B;
    int n=a.size()+b.size()-1,lim=Glim(n);
    P.resize(lim);Q.resize(lim);A.resize(lim);B.resize(lim);
    for(int i=0;i<a.size();i++)P[i].x=a[i].x;
    for(int i=0;i<b.size();i++)P[i].y=b[i].x;
    FFT(P,rt,lim);Q[0]=~P[0];
    for(int i=1;i<lim;i++)Q[i]=~P[lim-i];
    for(int i=0;i<lim;i++)
        A[i]=(P[i]+Q[i])*(cp){1.0/2,0},
        B[i]=(P[i]-Q[i])*(cp){0,-1.0/2};
    for(int i=0;i<lim;i++)A[i]=A[i]*B[i];
    FFT(A,irt,lim);A.resize(n);
    for(int i=0;i<n;i++)A[i].x=(int)(A[i].x/lim+0.5);
    return A;
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
    vec A,B;A.resize(n+1);B.resize(m+1);
    for(int i=0;i<=n;i++)A[i].x=a[i];
    for(int i=0;i<=m;i++)B[i].x=b[i];
    A=A*B;
    for(int i=0;i<A.size();i++)c[i]=A[i].x;
	// c[0] = sin(a[0]) * 998244353;
	// c[1] = cos(b[0]) * 104857601;
}

评测结果