HDU - 1402 A * B Problem Plus FFT裸题

http://acm.hdu.edu.cn/showproblem.php?pid=1402

题意:

　　求$a*b$ 但是$a$和$b$的范围可以达到 $1e50000$

题解:

　　显然...用字符串模拟的大数或者压位的大数是无法胜任这种计算的....

　　然后,2个大整数相乘,可以理解为卷积,所以就用快速傅里叶变换(FFT)来加速他

　　模板题

　　简单总结一下对FFT的认知:

FFT用于算卷积,卷积可以理解为两个多项式相乘
显然复杂度是$O(n^2)$的但是fft可以优化为$O(nlogn)$
如何优化,
考虑2个点确定直线,3个点确定抛物线,$n+1$个点确定了$n$次多项式
我们用$n+1$个点$(x_i,y_i)$表达了原来的式子
如何用点值表达卷积(多项式相乘)?
式子展开可以知道,$x_i$确定的时候,对于点值表达式就对应了点$(x_i,f(x_i)*g(x_i))$
也就是可以$O(1)$得到一个点答案,$n$个点就是$O(n)$
那问题又来了,$n+1$个点的$(x_i,y_i)$,每次求解一次多项式的值,需要$O(n)$
也就是$O(n^2)$复杂度,依然超时
所以,现在考虑如何快速的算多项式的值
因为$x_i$我们可以自己定义,因此利用虚根的特殊性质,我们就能分治处理了
就可以复杂度$O(nlogn)$的得到点值表达式
然后$O(n)$的算点值表达式的值
然后逆运算回到答案

#include <bits/stdc++.h>

#define ll long long

#define usd unsigned

#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define rep(ii,a,b) for(int ii=a;ii<=b;++i)

#define per(ii,a,b) for(int ii=b;ii>=a;--i)

#define show(x) cout<<#x<<"="<<x<<endl

#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl

#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl

#define show4(w,x,y,z) cout<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl

#define showa(a,b) cout<<#a<<'['<<b<<"]="<<a[b]<<endl

#define pii pair<int,int>

#define cp complex<double>//<complex>头文件里的东西

using namespace std;

const int maxn=2e5+10;

const int maxm=2e6+10;

const int INF=0x3f3f3f3f;

const int mod=1e9+7;

int casn,n,m,k;

const double pi=acos(-1.0);

int lena,lenb,len,pw,ans[maxn],rr[maxn];

cp a[maxn] ,b[maxn];

char sa[maxn],sb[maxn];

void fft(cp *a,int f){//递归分治太慢,用迭代实现

	rep(i,0,n-1) if(i<rr[i]) swap(a[i],a[rr[i]]);//分治原来的数组

	for(int i=1;i<n;i<<=1){

		cp wn(cos(pi/i),sin(f*pi/i)),x,y;//计算虚根

		for(int j=0;j<n;j+=(i<<1)){

			cp w(1,0);

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

				x=a[j+k],y=w*a[i+j+k];

				a[j+k]=x+y;

				a[i+j+k]=x-y;

			}

		}

	}

}

int main(){

	while(~scanf("%s%s",sa,sb)){

		n=1;

		len=pw=0;

		memset(ans,0,sizeof ans);

		lena=strlen(sa);

		lenb=strlen(sb);

		while(n<=lena+lenb) n<<=1,++pw;

		rep(i,0,lena-1) a[i]=sa[lena-i-1]-'0';

		rep(i,lena,n) a[i]=0;

		rep(i,0,lenb-1) b[i]=sb[lenb-i-1]-'0';

		rep(i,lenb,n) b[i]=0;

		rep(i,0,n) rr[i]=(rr[i>>1]>>1)|((i&1)<<(pw-1));//分治中的二进制规律,因此预处理参数

		fft(a,1);//DFT a

		fft(b,1);//DFT b

		rep(i,0,n) a[i]*=b[i];

		fft(a,-1);//IDFT a*b

		rep(i,0,lena+lenb) {

			ans[i]+=int(a[i].real()/n+0.5);

			ans[i+1]+=ans[i]/10;

			ans[i]%=10;

			if(ans[i]>0) len=i;

		}

		per(i,0,len){

			putchar (ans[i]+'0');

		}

		puts("");

	}

  return 0;

}

巴特西

HDU - 1402 A * B Problem Plus FFT裸题

最新文章

热门文章