洛谷不支持中文?重新发一下代码
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#define esp (1e-8)
#define maxint (2147483647)
#define pi (3.141592653589793)
#define l(a) ((a)<<1)
#define r(a) ((a)<<1|1)
#define b(a) (1<<(a))
#define rep(i,a,b) for(int i=a;i<=(b);i++)
#define clr(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
int readint(){
int t=0,f=1;char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)){
t=(t<<3)+(t<<1)+c-'0';
c=getchar();
}
return t*f;
}
ll readll(){
ll t=0ll,f=1ll;char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1ll;
c=getchar();
}
while(isdigit(c)){
t=(t<<3ll)+(t<<1ll)+ll(c-'0');
c=getchar();
}
return t*f;
}
const int maxn=5000009;
int n,m;
struct complex{
double r,i;
inline complex(double R,double I){
r=R;i=I;
}
inline complex(){
r=0;i=0;
}
inline void out(){
if(abs(i)>esp) printf("%.2lf %.2lfi\n",r,i);
else printf("%.2lf\n",r);
}
inline complex operator +(const complex A)const{
return complex(r+A.r,i+A.i);
}
inline complex operator -(const complex A)const{
return complex(r-A.r,i-A.i);
}
inline complex operator *(const complex A)const{
return complex(r*A.r-i*A.i,i*A.r+r*A.i);
}
}a[maxn],b[maxn];
int init(int t){
int T=0;
for(T=0;b(T)<t;T++);
return b(T);
}
complex*FFT(complex a[],int t,int opt){
if(t==1) return a;
complex w=complex(1,0),w1=complex(cos(2*pi/t),sin(2*pi/t*opt));
complex*a0=new complex[t>>1],*a1=new complex[t>>1];
rep(i,0,t-1){
if(i&1) a1[i>>1]=a[i];
else a0[i>>1]=a[i];
}
complex*y0=FFT(a0,t>>1,opt),*y1=FFT(a1,t>>1,opt),*y=new complex[t];
rep(i,0,(t>>1)-1){
y[i]=y0[i]+w*y1[i];
y[i+(t>>1)]=y0[i]-w*y1[i];
w=w*w1;
}
delete(a0);delete(a1);delete(y0);delete(y1);
return y;
}
complex*DFT(complex a[],int t,int opt){
t=init(t);
complex*ans=new complex[t];
ans=FFT(a,t,opt);
if(opt==-1) rep(i,0,t-1){
(ans+i)->r/=t;(ans+i)->i/=t;
}
return ans;
}
int main(){
//freopen("#intput.txt","r",stdin);
//freopen("#output.txt","w",stdout);
n=readint();m=readint();n++;m++;
rep(i,0,n-1) a[i].r=readint();
rep(i,0,m-1) b[i].r=readint();
int N=max(n,m);N=init(N)<<1;
complex*A=DFT(a,N,1),*B=DFT(b,N,1);
rep(i,0,N-1) *(A+i)=(*(A+i))*(*(B+i));
A=DFT(A,N,-1);N--;
while(abs((A+N)->r)<esp) N--;
rep(i,0,N){
printf("%.0lf",(A+i)->r);
putchar(i==N?'\n':' ');
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
```
by ChenThree @ 2017-11-06 17:24:28
**###更好发挥更符合法规和法国**
by 雷豹 @ 2017-11-06 17:34:08
我的递归版本也RE了,估计 1e6 的大数据递归会爆栈。
by 拓拓 @ 2017-11-16 23:37:05
我NTT也RE了。。。
by 向金牌冲刺 @ 2018-01-27 07:43:57
法法
by Willem @ 2018-02-14 16:59:42