此代码能否继续将FFT次数优化至一次
查看原帖
此代码能否继续将FFT次数优化至一次
1288642
lmn985楼主2025/8/2 07:54
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int ret=0;
void write(int x,int k){
	ret++;
    if(x>9)write(x/10,k);
    else {
    	k-=ret;
    	while((k--)>0)putchar('0');
	}
    putchar(x%10+'0');
    return;
}
const double PI=3.1415926535;
const int N=1<<21;
int ans[N],rev[N];
complex<double> xa[N],w_table[N];
void FFT(complex<double> a[],int n,int inv){
    rep(i,0,n)if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int mid=1;mid<n;mid<<=1){
        double ag=PI/mid;
        complex<double> wn(cos(ag),-inv*sin(ag)),w(1,0);
        rep(j,0,mid)w_table[j]=w,w*=wn;
        for(int i=0;i<n;i+=mid*2)rep(j,0,mid){
            complex<double> x=a[i+j],y=w_table[j]*a[i+j+mid];
            a[i+j]=x+y,a[i+j+mid]=x-y;
        }
    }
    if(inv==-1)rep(i,0,n)a[i]/=n;
}
void hpm(string a,string b){
    if(a=="0"||b=="0"){cout<<'0';return;}
    reverse(a.begin(),a.end()),reverse(b.begin(),b.end());
    int la=0,lb=0;
    for(int i=0;i<a.size();i+=2){
        int num=0;
        if(i<a.size())num+=a[i]-'0';
        if(i+1<a.size())num+=10*(a[i+1]-'0');
		xa[la].real(num);
		la++;
    }
    for(int i=0;i<b.size();i+=2){
        int num=0;
        if(i<b.size())num+=b[i]-'0';
        if(i+1<b.size())num+=10*(b[i+1]-'0');
		xa[lb].imag(num);
		lb++;
    }
    int len=1,bit=0;
    while(len<la+lb)len<<=1,bit++;
    rep(i,0,len)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    FFT(xa,len,1);
    rep(i,0,len)xa[i]=xa[i]*xa[i];
    FFT(xa,len,-1);
    rep(i,0,len)ans[i]=(int)(xa[i].imag()/2+0.5);
    rep(i,0,len-1)ans[i+1]+=ans[i]/100;
    int pos=len-1;
    while(pos>0&&ans[pos]==0)pos--;
    write(ans[pos]%100,0);
    for(int i=pos-1;i>=0;i--)ret=0,write(ans[i]%100,2);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string a,b;
    cin>>a>>b;
    hpm(a,b);
    return 0;
}
2025/8/2 07:54
加载中...