FFT求调
查看原帖
FFT求调
723517
Joseph__Joestar楼主2022/7/9 16:10

样例输出都是0; 不知道该怎么改; 蒟蒻只会被板子;

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const double pi=acos(-1.0);	
const int maxn=100005;
struct complex
{
	double x,y;
	complex(double xx=0,double yy=0)
	{
		x=xx;
		y=yy;
	}
}a[maxn],b[maxn];
complex  operator + (complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex  operator - (complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex  operator * (complex a,complex b){return complex(a.x*b.x-a.y*b.y,b.y*a.x+a.y*b.x);}
int limit=1;
int r[maxn];
int l;
void FFT(complex *A,int type)
  {
  	for(int i=1;i<=limit;i++)
  	  if(i<r[i])
  	  swap(a[i],a[r[i]]);
  	for(int mid=1;mid<limit;mid<<=1)
	  {
	    complex Wn(cos(pi/mid),type*sin(pi/mid));
	    for(int r=mid<<1,j=1;j<=limit;j+=r)
		  {
		    complex w(1,0);
		    for(int k=1;k<=mid;k++,w=w*Wn)
		      {
		    	complex x=a[j+k],y=w*a[j+mid+k];
		    	a[j+k]=x+y;
		    	a[j+mid+k]=x-y;
			  } 
		  }  
	  } 
  }
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
    for(int i=1;i<=n+1;i++)
	  scanf("%d",&a[i].x);
	for(int i=1;i<=m+1;i++)
	   scanf("%d",&b[i].x);
	while(limit<=n+m)
	    limit<<=1,
	    l++;
	for(int i=1;i<=limit;i++)
	  {
	  	r[i]=(r[i>>1]>>1)|((i&1)<<l-1);
	  }
	FFT(a,1);
	FFT(b,1);
	for(int i=1;i<=limit+1;i++)
	  a[i]=a[i]*b[i];
	FFT(a,-1);
	for(int i=1;i<=n+m+1;i++)
	   printf("%d ",(int)(a[i].x/limit+0.5));
	   return 0;  
}  ```
2022/7/9 16:10
加载中...