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

题目

题目链接：https://www.luogu.com.cn/problem/P1919
给出两个数 \(a,b\)，求 \(a\times b\)。

思路

类比列竖式的时候，从低位往高位数，分别为 \(i,j\) 两位的数字相乘会到第 \(i+j-1\) 位。
这其实就是一个卷积的形式，直接上 FFT 即可。
注意需要在跑完 FFT 之后进位。
时间复杂度 \(O(n\log n)\)。

代码

#include <bits/stdc++.h>
#define cp complex<double>
using namespace std;

const int N=3000010;
const double pi=acos(-1);
int n,m,Maxn=1,rev[N],h[N];
char ch[N];
cp f[N],g[N];

void fft(cp *f,int tag)
{
	for (int i=0;i<Maxn;i++)
		if (i<rev[i]) swap(f[i],f[rev[i]]);
	for (int mid=1;mid<Maxn;mid<<=1)
	{
		cp temp(cos(pi/mid),tag*sin(pi/mid));
		for (int i=0;i<Maxn;i+=(mid<<1))
		{
			cp w(1,0);
			for (int j=0;j<mid;j++,w*=temp)
			{
				cp x=f[i+j],y=w*f[i+j+mid];
				f[i+j]=x+y; f[i+j+mid]=x-y;
			}
		}
	}
}

int main()
{
	scanf("%s",ch); n=strlen(ch);
	for (int i=0;i<n;i++) f[i]=cp(1.0*(ch[n-i-1]-48),0.0);
	scanf("%s",ch); m=strlen(ch);
	for (int i=0;i<m;i++) g[i]=cp(1.0*(ch[m-i-1]-48),0.0);
	n+=m;
	while (Maxn<=n) Maxn<<=1;
	for (int i=0;i<Maxn;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)?(Maxn>>1):0);
	fft(f,1); fft(g,1);
	for (int i=0;i<Maxn;i++) f[i]*=g[i];
	fft(f,-1);
	for (int i=0;i<=Maxn;i++)
	{
		h[i]+=(int)(f[i].real()/Maxn+0.4999);
		if (i==Maxn && h[i]>9) Maxn++;
		h[i+1]=h[i]/10; h[i]%=10;
	}
	int i=Maxn;
	while (!h[i] && i) i--;
	for (;i>=0;i--) printf("%d",h[i]);
	return 0;
}