FFT求助
查看原帖
FFT求助
230804
Durancer楼主2021/3/3 09:05

样例和#1本地测着没问题,但是交上去显示第一位是"-",求找错qwq

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
const int N=2e6+9;
const double Pi=acos(-1.0);
char s1[N],s2[N];
int r[N];
int ans[N];
int lim=1,l=0;
int n,m;
struct Complex{
	double x;
	double y;
	Complex(double kx=0,double ky=0)
	{
		x=kx;
		y=ky;
	}
}a[N],b[N];
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,a.x*b.y+a.y*b.x);}
void FFT(Complex *A,int type)
{
	for(register int i=0;i<lim;i++)
		if(i<r[i]) swap(A[i],A[r[i]]);
	for(register int mid=1;mid<lim;mid<<=1)
	{
		Complex Wn(cos(Pi/mid),type*sin(Pi/mid));
		for(register int R=mid<<1,j=0;j<lim;j+=R)
		{
			Complex w(1,0);
			for(register int k=0;k<mid;k++,w=w*Wn)
			{
				Complex x=A[j+k];
				Complex y=w*A[j+k+mid];
				A[j+k]=x+y;
				A[j+k+mid]=x-y;
				}	
		}	
	}
} 
int main()
{
	scanf("%s%s",s1,s2);
	n=strlen(s1);
	m=strlen(s2);
	int kkk_sc0003=0;
	for(register int i=n-1;i>=0;i--)
	{
		a[kkk_sc0003].x=s1[i]-'0';
		kkk_sc0003++;	
	} 
	kkk_sc0003=0;
	for(register int i=m-1;i>=0;i--)
	{
		b[kkk_sc0003].x=s2[i]-'0';
		kkk_sc0003++;
	}
	while(lim<=n+m-2)
	{
		lim<<=1;
		l++;	
	} 
	for(register int i=0;i<lim;i++)
		r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(a,1);
	FFT(b,1);
	for(register int i=0;i<lim;i++)
		a[i]=a[i]*b[i];
	FFT(a,-1);
	for(register int i=0;i<=lim;i++)
	{
		ans[i]+=(int)(a[i].x/lim+0.5);
		if(ans[i]>9)
		{
			ans[i+1]+=(ans[i]/10);
			ans[i]%=10;
			if(i==lim) lim++; 
		}
	}
	while(!ans[lim]&&lim>=1) lim--;
	for(register int i=lim;i>=0;i--)
		printf("%d",ans[i]);
	return 0;
}
2021/3/3 09:05
加载中...