FFT 90pts求调
查看原帖
FFT 90pts求调
482610
Mortidesperatslav楼主2024/1/17 17:57
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct mycomplex{
	double x,y;
	mycomplex(double tmpx=0,double tmpy=0){this->x=tmpx,this->y=tmpy;}
	mycomplex operator+(mycomplex b){
		return{this->x+b.x,this->y+b.y};
	}
	mycomplex operator-(mycomplex b){
		return{this->x-b.x,this->y-b.y};
	}
	mycomplex operator*(mycomplex b){
		return{this->x*b.x-this->y*b.y,this->x*b.y+this->y*b.x};
	}
}a[3000005],b[3000005];
int n,m,l,r[3000005],ans[3000005],p;
int lim=1;
double pi=3.1415926535897932;
string aa,bb;
void FFT(mycomplex *aa,int tp){
	for(int i=0;i<lim;i++)if(i<r[i])swap(aa[i],aa[r[i]]);
	for(int mid=1;mid<lim;mid<<=1){
		mycomplex omega(cos(pi/mid),tp*sin(pi/mid));
		for(int rr=mid<<1,j=0;j<lim;j+=rr){
			mycomplex omega2(1,0);
			for(int k=0;k<mid;k++,omega2=omega2*omega){
				mycomplex xx=aa[j+k],yy=omega2*aa[j+k+mid];
			//	cout<<xx.x<<" "<<xx.y<<" "<<yy.x<<" "<<yy.y<<"\n";
				aa[j+k]=xx+yy;
				aa[j+k+mid]=xx-yy;
			//	cout<<aa[j+k].x<<" "<<aa[j+k].y<<"\n";
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>aa>>bb;
	n=aa.size()-1;
	m=bb.size()-1;
	for(int i=0;i<=n;i++)a[i].x=aa[n-i]-'0';
	for(int i=0;i<=m;i++)b[i].x=bb[m-i]-'0';
	while(lim<=n+m)lim<<=1,l++;
	for(int i=0;i<lim;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(a,1);
	FFT(b,1);
	for(int i=0;i<=lim;i++)a[i]=a[i]*b[i];
	FFT(a,-1);
	for(int i=0;i<=n+m;i++)ans[i]=(int)(a[i].x/lim+0.5);
	for(int i=0;i<=n+m+1;i++)
		if(ans[i]>10){
			ans[i+1]+=ans[i]/10;
			ans[i]%=10;
		}
	int h=n+m+2;
	while(ans[h]==0)h--;
	while(h>=0){
		cout<<ans[h];
		h--;
	}
}
2024/1/17 17:57
加载中...