【洛谷P1919】A*B Problem升级版

题目大意：rt

题解：将长度为 N 的大整数看作是一个 N-1 次的多项式，利用 FFT 计算多项式的卷积即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

typedef complex<double> cp;

const int maxn=2e5+10;

const double pi=acos(-1);

int n,tot=1,bit,rev[maxn],ans[maxn];

cp a[maxn],b[maxn];

char s[maxn];

void read_and_parse(){

	scanf("%d%s",&n,s),--n;

	for(int i=0;i<=n;i++)a[i]=s[n-i]-'0';

	scanf("%s",s);

	for(int i=0;i<=n;i++)b[i]=s[n-i]-'0';

}

void fft(cp *t,int type){

	for(int i=0;i<tot;i++)if(i<rev[i])swap(t[i],t[rev[i]]);

	for(int mid=1;mid<tot;mid<<=1){

		cp wn(cos(pi/mid),type*sin(pi/mid));

		int len=mid<<1;

		for(int j=0;j<tot;j+=len){

			cp w(1,0);

			for(int k=0;k<mid;k++,w*=wn){

				cp x=t[j+k],y=w*t[j+mid+k];

				t[j+k]=x+y,t[j+mid+k]=x-y;

			}

		}

	}

}

void solve(){

	int m=2*n;

	while(tot<=m)tot<<=1,++bit;

	for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));

	fft(a,1),fft(b,1);

	for(int i=0;i<tot;i++)a[i]=a[i]*b[i];

	fft(a,-1);

	for(int i=0;i<tot;i++)ans[i]=(int)(a[i].real()/tot+0.5);

	for(int i=0;i<tot;i++)ans[i+1]+=ans[i]/10,ans[i]%=10;

	while(tot>0&&!ans[tot])--tot;

	for(int i=tot;~i;i--)printf("%d",ans[i]);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【洛谷P1919】A*B Problem升级版

最新文章

热门文章