@[Turkey](/space/show?uid=43785) 模板题数据不强，让你以后做题都用错误的模板？
by IsaacOriGuo @ 2017-09-24 17:02:10
@[Turkey](/space/show?uid=43785) 树状数组题让你用for循环AC？
by λᴉʍ @ 2017-09-24 17:03:23
@[Turkey](/space/show?uid=43785) 模板题数据不强，让你用常数巨大的写法AC了，等以后正式比赛被卡你就。。。。
by IsaacOriGuo @ 2017-09-24 17:05:49
可是我高精乘法fft过了这里过不了
by Turkey @ 2017-09-24 18:12:16
@[XZZ\_\_233](/space/show?uid=23118) 那我请您帮我看看怎么优化好么我是没什么办法
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define pi acos(-1)
using namespace std;
const int ma=4000006;
int read(){
char ch=getchar();
int a=0,b=1;
while(!(ch<='9'&&ch>='0')){
if(ch=='-')b=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
a=(a<<1)+(a<<3)+(ch^'0');
ch=getchar();
}
return a*b;
}
int n,m,l;
struct complex{
double r,i;
complex (double real=0.0,double image=0.0){
r=real;i=image;
}
complex operator - (const complex o){
return complex(r-o.r,i-o.i);
}
complex operator + (const complex o){
return complex(r+o.r,i+o.i);
}
complex operator * (const complex o){
return complex(r*o.r-i*o.i,r*o.i+i*o.r);
}
}a[ma],b[ma];
void brc(complex *y,int l){
for(int i=1,j=l/2;i<l-1;i++){//一定是l-1不然死循环了
if(i<j)swap(y[i],y[j]);
int k=l/2;
while(j>=k){
j-=k;
k/=2;
}
j+=k;
}
}
void fft(complex *y,int l,int on){
brc(y,l);complex u,t;
for(int i=2;i<=l;i<<=1){
complex wn(cos(2*pi*on/i),sin(2*pi*on/i));
for(int j=0;j<l;j+=i){
complex w(1,0);
for(int k=j;k<j+i/2;k++){
u=y[k];t=w*y[k+i/2];
y[k]=u+t;y[k+i/2]=u-t;
w=wn*w;
}
}
}
if(on==-1)for(int i=0;i<l;i++)y[i].r/=l;
}
int main()
{
// freopen("1.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++){
int x;
x=read();
a[i].r=x;a[i].i=0.0;
}
for(int j=0;j<=m;j++){
int x;
x=read();
b[j].r=x;b[j].i=0.0;
}
l=1;
while(l<n+m+2)l<<=1;
fft(a,l,1);fft(b,l,1);
for(int i=0;i<=l;i++)a[i]=a[i]*b[i];
fft(a,l,-1);
for(int i=0;i<n+m+1;i++)printf("%.0lf ",(a[i].r+0.1));
return 0;
}
```
by Turkey @ 2017-09-24 18:21:30
@[Turkey](/space/show?uid=43785) 不会fft，我想你压常压的太少了、、、
by λᴉʍ @ 2017-09-24 20:32:16
@[XZZ\_\_233](/space/show?uid=23118) 这题数据确实强。。。。。
by yyb_test @ 2017-09-28 12:48:41
@[yyb\_test](/space/show?uid=48618) 惊现省选yyb大佬
by IsaacOriGuo @ 2017-09-28 12:50:59
可是你的代码现在能过了(大雾
by misinclair @ 2018-04-18 21:07:21