FFT全RE求助
查看原帖
FFT全RE求助
285373
abuyao楼主2021/4/11 12:07
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
typedef long double lf;
using std::swap;
const lf pi=acos(-1.0);
struct cpl{
	lf x,y;
	cpl(lf x=0.0,lf y=0.0){this->x=x,this->y=y;}
	inline cpl operator+(const cpl a)const{return cpl(x+a.x,y+a.y);}
	inline cpl operator-(const cpl a)const{return cpl(x-a.x,y-a.y);}
	inline cpl operator*(const cpl a)const{return cpl(x*a.x-y*a.y,x*a.y+y*a.x);}
};
inline void Change(cpl a[],int l){
	int i,j,k;
	for(i=1,j=l>>1;i<l-1;i++){
		if(i<j)swap(a[i],a[j]);
		k=l>>1;
		while(j>=k)j-=k,k>>=1;
		if(j<k)j+=k;
	}
}
inline void FFT(cpl a[],int l,int tp){
	Change(a,l);
	for(int i=2;i<=l;i<<=1){
		cpl wn(cos(2*pi/i),sin(tp*2*pi/i));
		for(int j=0;j<l;j+=i){
			cpl w(1.0,0.0);
			for(int k=j;k<(i>>1)+j;k++){
				cpl u=a[k];
				cpl v=w*a[k+(i>>1)];
				a[k]=u+v;
				a[k+(i>>1)]=u-v;
				w=w*wn;
			}
		}
	}
	if(tp==-1)for(int i=0;i<l;i++)a[i].x/=l;
}
const int N=1e6+6,M=N<<1;
char a[N],b[N];
int l1,l2,l=1,c[N];
cpl x[M],y[M];
int main(){
	scanf("%s%s",a,b);
	l1=strlen(a);
	l2=strlen(b);
	while(l<l1<<1||l<l2<<1)l<<=1;
	for(int i=0;i<l1;i++)x[i].x=a[l1-i-1]-48.0;
	for(int i=0;i<l2;i++)y[i].x=b[l2-i-1]-48.0;
	FFT(x,l,1);
	FFT(y,l,1);
	for(int i=0;i<l;i++)x[i]=x[i]*y[i];
	FFT(x,l,-1);
	for(int i=0;i<l;i++)c[i]=int(x[i].x+0.5);
	for(int i=0;i<l;i++)c[i+1]+=c[i]/10,c[i]%=10;
	l=l1+l2-1;
	while(l>0&&!c[l])l--;
	for(int i=l;~i;i--)putchar(c[i]+48);
	return 0;
}

RT,求调QwQ

2021/4/11 12:07
加载中...