萌新刚学OI,求助FFT
查看原帖
萌新刚学OI,求助FFT
231169
Laser_Crystal楼主2020/8/1 14:51

Rt,布吉岛哪里错惹,求大佬帮忙康康/kel

#include<bits/stdc++.h> 
using namespace std;
const double pi=acos(-1.0);
const int maxn=1e7+7;
int n,m;
int l,rev[maxn];
int size=1;
inline int read()
{
	char c=getchar();
	int x=0,f=1;
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
struct CP
{
	double x,y;
	CP (double xxs=0,double yy=0) {x=xxs,y=yy;};
}a[maxn],b[maxn];
CP operator + (CP a,CP b) {return CP(a.x+b.x,a.y+b.y);}
CP operator - (CP a,CP b) {return CP(a.x-b.x,a.y-b.y);}
CP operator * (CP a,CP b) {return CP(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}	
inline void FFT(CP *a,int k)
{
	for(register int i=0;i<size;i++)
		if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(register int mid=1;mid<size;mid*=2)
	{
		CP Wn(cos(pi/mid),k*sin(pi/mid));
		for(register int j=0;j<size;j+=mid*2)
		{
			CP w(1,0);
			for(register int t=0;t<mid;t++)
			{
				w=w*Wn;
				CP x=a[j+t],y=w*a[j+mid+t];
				a[j+t]=x+y;
				a[j+mid+t]=x-y;
			}
		}
	}
}
int main()
{
	int n,m;
	n=read(),m=read();
	for(register int i=0;i<=n;i++) a[i].x=read();
	for(register int i=0;i<=m;i++) b[i].x=read();
	while(size<=m+n) size*=2,l++;
	for(register int i=0;i<size;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	FFT(a,1),FFT(b,1);
	for(register int i=0;i<=size;i++) a[i]=a[i]*b[i];
	FFT(a,-1);
	for(int i=0;i<=n+m;i++)
	printf("%d ",(int)(a[i].x/size+0.5));
	return 0;
}

能否不要无意义回复qwq

2020/8/1 14:51
加载中...