求助压位FFT
  • 板块学术版
  • 楼主xzy_caiji
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/5 10:47
  • 上次更新2024/8/5 11:30:48
查看原帖
求助压位FFT
939580
xzy_caiji楼主2024/8/5 10:47
#include<bits/stdc++.h>
//#pragma GCC optimize(3)
#define cp complex<double>
#define maxn 2097153
const double pi=3.14159265; 
using namespace std;
cp a0[1048577];
cp omega(int n,int k,int inv){
    return cp(cos(pi*k/n),inv*sin(pi*k/n));
}
cp omg; 
void FFT(cp *a,int n,int inv){
	if(n==1)return;
	int m=n>>1;
	for(int i=0;i<m;i++)a[i]=a[i<<1],a0[i]=a[i<<1|1];
	for(int i=m;i<n;i++)a[i]=a0[i-m];
	FFT(a,m,inv);
	FFT(a+m,m,inv);
	for(int i=0;i<m;i++){
		omg=omega(m,i,inv)*a[i+m];
		a[i+m]=a[i]-omg;
		a[i]+=omg;
	}
}
int res[maxn];
cp aa[maxn];char a[1000005],b[1000005];
void yawei(int al,int bl,int &n){
	int cnt=0,i;
	for(i=al-1;i>0;i-=2)aa[cnt++].real((a[i-1]-48)*10+a[i]-48);
	if(al&1)aa[cnt].real(a[0]-48),cnt++;
	int cnt2=0;
	for(i=bl-1;i>0;i-=2)aa[cnt2++].imag((b[i-1]-48)*10+b[i]-48);
	if(bl&1)aa[cnt2].imag(b[0]-48),cnt2++;
	while(n<cnt+cnt2)n<<=1;
}
int main(){
	//freopen("data.innn","r",stdin);
	scanf("%s%s",a,b);
	int n=1,alen=strlen(a),blen=strlen(b);
	yawei(alen,blen,n);
	FFT(aa,n,1);
	for(int i=0;i<n;i++)aa[i]*=aa[i];
	FFT(aa,n,-1);
	int nn=alen+blen;
	for(int i=0;i<nn;i++){
		res[i]+=int(aa[i].imag()/n+1)>>1;
		res[i+1]=res[i]/100;
		res[i]%=100;
	}
	for(int i=nn-1;i>=0;i--){
		printf("%c",char(res[i]/10+48));
	   printf("%c",char(res[i]%10+48));
	}
}
2024/8/5 10:47
加载中...