RT,66分,WA三个点 评测记录

https://www.luogu.com.cn/paste/hgwysl6g

#include<iostream>
#include<complex>
#include<cstdio>
using namespace std;
const int N=2200000;
inline int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
int n,m,rev[N];
complex<double> f[N],g[N];
void MakeRev(int n){ for(int i=1;i<=(1<<n);++i) rev[i]=(rev[i>>1]>>1)+((i&1)<<(n-1));}
#define len (1<<lglen)
const double Pi=3.1415926;
void FFT(complex<double> *f,int n,int type){
	for(int i=0;i<n;++i) if(i<rev[i]) swap(f[i],f[rev[i]]);//i and rev[i] yiyiduiying
	for(int lglen=1;len<=n;++lglen){
		complex<double> w0=cos(2*Pi/len)+type*sin(2*Pi/len)*1i;
		for(int i=0;i<n;i+=len){//solve i~i+len-1
			//f(x)=ls(x^2)+x*rs(x^2)
			//f(w_len^k)      =f1(w_len/2^k)+w_len^k*f2(w_len/2^k) 
			//f(w_len^k+len/2)=f1(w_len/2^k)-w_len^k*f2(w_len/2^k)
			complex<double> u,v,w=1;
			for(int k=0;k<(len>>1);++k){
				u=f[i+k];v=w*f[i+k+(len>>1)];
				f[i+k]=u+v;f[i+k+(len>>1)]=u-v;
				w=w*w0;
			}
		}
	}
	if(type==-1) for(int i=0;i<n;++i) f[i]/=n;
}
int main(){
	n=read();m=read();
	for(int i=0;i<=n;++i) f[i]=read();
	for(int i=0;i<=m;++i) g[i]=read();
	m+=n;//f*g = O(x^(m+n)) 
	for(n=0;(1<<n)<=m;++n);MakeRev(n);n=(1<<n);//n is min{x is pow of 2|x>m}
	FFT(f,n,1);FFT(g,n,1);
	for(int i=0;i<n;++i) f[i]*=g[i];
	FFT(f,n,-1);
	for(int i=0;i<=m;++i) printf("%d ",int(f[i].real()+0.5));
	return 0;
}