原题链接 ( AcWing版 )

原题链接 ( 洛谷版 )

题目描述

给定两个正整数 A A A 和 B B B，请你计算 A × B A×B A×B 的值。

输入格式

共两行，第一行包含整数 A A A，第二行包含整数 B B B。

输出格式

共一行，包含 A × B A×B A×B 的值。

数据范围

1 ≤ A 1 ≤ A 1≤A 与 B B B 的长度 ≤ 1 0 5 10^5 105。

输入样例：

2
3

输出样例：

6

强烈推荐这个视频：快速傅里叶变换(FFT)——有史以来最巧妙的算法？

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
const double pi=acos(-1.0);
char s1[N],s2[N]; int n,m,res[N],k,p,bit,rev[N];
struct C{
	double x,y;
	C operator+(const C& t){ return {x+t.x,y+t.y}; }
	C operator-(const C& t){ return {x-t.x,y-t.y}; }
	C operator*(const C& t){ return { x*t.x-y*t.y,x*t.y+y*t.x }; }
}a[N],b[N];

void fft(C* a,int n,int inv){	//递归版
	if(n==1)	return;
	C l[n>>1],r[n>>1];
	for(int i=0;i<(n>>1);i++) l[i]=a[i<<1],r[i]=a[i<<1|1];
	fft(l,n>>1,inv);	fft(r,n>>1,inv);
	C wn{cos(2*pi/n),inv*sin(2*pi/n)},w{1,0};
	for(int i=0;i<(n>>1);i++,w=w*wn)
		a[i]=l[i]+w*r[i], a[i+(n>>1)]=l[i]-w*r[i];
}

void fft(C* a,int inv){		//迭代版
	for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int mid=1;mid<n;mid<<=1){
		C wn={cos(pi/mid),inv*sin(pi/mid)};
		for(int i=0;i<n;i+=mid<<1){
			C w={1,0};
			for(int j=0;j<mid;j++,w=w*wn){
				C x=a[i+j],y=w*a[i+j+mid];
				a[i+j]=x+y,a[i+j+mid]=x-y;
			}
		}
	}
}

int main(){
	scanf("%s%s",s1,s2);
	n=strlen(s1),m=strlen(s2);
	for(int i=0;i<n;i++)	a[i].x=s1[i]-'0';
	for(int i=0;i<m;i++)	b[i].x=s2[i]-'0';
	for(m=n+m,bit=1;(1<<bit)<m;bit++);	n=(1<<bit);
	for(int i=1;i<n;i++)	//rev数组在迭代FFT时需要用到
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	fft(a,1);	fft(b,1);
	for(int i=0;i<n;i++)	a[i]=a[i]*b[i];
	fft(a,-1);
	reverse(a,a+m-1);
	for(p=0;p<m-1||k;p++){
		res[p]=((int)(a[p].x/n+0.5+k))%10;
		k=(a[p].x/n+0.5+k)/10;
	}
	for(p--;p>=0;p--) printf("%d",res[p]);
}

注意

这题数组要稍微开大些。AcWing上两种方法都可以过，洛谷上只有迭代版可以过。

代码细节解释

• r e v rev rev 数组在迭代 F F T FFT FFT 时会用到，具体作用参考下图。画的图有点丑。

• 关于 r e v rev rev 的求法也有递推的思想， r e v [ i ] rev[i] rev[i] 与 r e v [ i > > 1 ] rev[i>>1] rev[i>>1] 有关。

• 行列式求逆的时候，多出来一个 1 n \frac1n n1​ ，所以最后求得的系数还要再除 n n n。
  

• for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
  这行代码中的if(i<rev[i])可以防止重复交换，不可以写为if(i!=rev[i])。

• C x=a[i+j],y=w*a[i+j+mid]; a[i+j]=x+y,a[i+j+mid]=x-y;
  这两行代码也不可以写成：
  a[i+j]=a[i+j]+w*[i+j+mid]; a[i+j+mid]=a[i+j]-w*a[i+j+mid];
  因为会修改 a [ i + j ] a[i+j] a[i+j] ，所以只能把 a [ i + j ] a[i+j] a[i+j] 与 a [ i + j + m i d ] a[i+j+mid] a[i+j+mid] 先保存起来。