Mn Zn 求助
查看原帖
Mn Zn 求助
115857
too_later楼主2021/6/3 20:08
#include<bits/stdc++.h>
#define I inline
#define RI register int
#define rep(i,a,b) for(RI i=a;i<=b;++i)
#define dow(i,a,b) for(RI i=a;i>=b;--i)
using namespace std;
const int N=8000005;
const double PI=acos(-1.0);
struct comp{
	double x,y;
	comp(double xx=0,double yy=0){ x=xx,y=yy; }
} a[N],b[N];
comp operator + (comp a,comp b){ return comp(a.x+b.x,a.y+b.y); }
comp operator - (comp a,comp b){ return comp(a.x-b.x,a.y-b.y); }
comp operator * (comp a,comp b){ return comp(a.x*b.x-a.y*b.y,a.x*b.y+b.x*a.y); }
int n,m,lim=1,cnt,lenc,lens,r[N];
char c[N],s[N],ans[N];
I void FFT(comp a[],int len,int op){
	rep(i,1,lim) if(r[i]>i) swap(a[r[i]],a[i]);
	for(RI l=1;l<len;l<<=1){
		comp now=comp(cos(PI/l),op*sin(PI/l));
		for(RI j=0;j<len;j+=(l<<1)){
			comp pw=comp(1,0);
			rep(k,0,l-1){
				comp x=a[j+k],y=pw*a[j+k+l];
				a[j+k]=x+y,a[j+k+l]=x-y;pw=pw*now;
			}
		}
	}
}
int main(){
	freopen("P1919_1.in","r",stdin);
	scanf("%s%s",c+1,s+1);lenc=strlen(c+1),lens=strlen(s+1);lenc--,lens--;
	while(lim<=(lenc+lens)) lim<<=1,cnt++;
	rep(i,1,N-1) r[i]=((r[i>>1]>>1)|((i&1)*(lim>>1)));
	dow(i,lenc,1) a[lenc-i+1].x=c[i]-'0';a[0].x=c[lenc+1]-'0';FFT(a,lim,1);
	dow(i,lens,1) b[lens-i+1].x=s[i]-'0';b[0].x=s[lens+1]-'0';FFT(b,lim,1);
	rep(i,0,lim) a[i]=a[i]*b[i];FFT(a,lim,-1);
//	rep(i,0,lim) printf("%d %lf\n",(int)(a[i].x/lim+0.5),a[i].y);
	rep(i,0,lim) ans[i]+=(int)(a[i].x/lim+0.5),ans[i+1]+=ans[i]/10,ans[i]%=10;
	bool flag=0;
	dow(i,lim,0){ if(!flag&&ans[i]) flag=1;if(flag) printf("%d",ans[i]);} 
	return 0;
}

个人认为 FFT 那部分没问题,不知道哪里 WA 掉了。

2021/6/3 20:08
加载中...