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

题目大意

给你两个超大整数 a , b a,b a,b，问 a ∗ b a*b a∗b
其中 a , b ≤ 1 0 1000000 a,b\leq10^{1000000} a,b≤101000000

思路

高精度都是狗
很明显，我们普通的高精度乘法不知道炸到哪里去了。
我们发现对于一个 n n n 位的十进制数 K K K，我们可以看做一个 n − 1 n-1 n−1 次的多项式，表示成 A ( x ) = a 0 + a 1 ∗ 10 + a 2 ∗ 1 0 2 + ⋅ ⋅ ⋅ + a n − 1 ∗ 1 0 n − 1 A(x)=a_0+a_1*10+a_2*10^2+···+a_{n-1}*10^{n-1} A(x)=a0​+a1​∗10+a2​∗102+⋅⋅⋅+an−1​∗10n−1
这样我们就可以把两个多项式卷积，就是乘起来， F F T FFT FFT 准备报到！

注意几个小细节：

为了方便，我们要把数倒序存储，因为我们在做 F F T FFT FFT 的时候多项式每一项的次数是递增的，而这里数的存储是从高位往低位存的，所以要逆序存储。
注意在加法的时候处理进位和前导 0 0 0
F F T FFT FFT 板子一定要背熟 (逃)

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#define r register
#define rep(i,x,y) for(r ll i=x;i<=y;++i)
#define per(i,x,y) for(r ll i=x;i>=y;--i)
using namespace std;
typedef long long ll;
const ll V=3e6+10;
const double pi=acos(-1.0); 
ll in()
{
	ll res=0,f=1;
	char ch;
	while((ch=getchar())<'0'||ch>'9')
	 if(ch=='-') f=-1;
	res=res*10+ch-48;
	while((ch=getchar())>='0'&&ch<='9')
	 res=res*10+ch-48;
	return res*f;
}
ll n,m,f[V];
ll now,k,ans[V];
char s1[V],s2[V];
struct complex 
{
	double x,y;//对应复数 a+bi 
	complex (double xx=0,double yy=0) { x=xx,y=yy; }
}a[V],b[V];
complex operator + (complex a,complex b) { return complex(a.x+b.x,a.y+b.y); }
complex operator - (complex a,complex b) { return complex(a.x-b.x,a.y-b.y); }
complex operator * (complex a,complex b) { return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); }
void FFT(complex *a,ll v)
{
	rep(i,0,now-1)
	 if(i<f[i]) swap(a[i],a[f[i]]);
	for(r ll mid=1;mid<now;mid<<=1)
	{
		complex Wn(cos(pi/mid),v*sin(pi/mid));//单位根 
		ll R=mid<<1;
		for(r ll j=0;j<now;j+=R)
		{
			complex val(1,0);
			for(r ll k=0;k<mid;++k,val=val*Wn)
			{
				complex x=a[j+k],y=val*a[j+mid+k];
				a[j+k]=x+y;
				a[j+mid+k]=x-y;
			}
		}
	}
}//这里和模板 FFT 一模一样
int main()
{
	scanf("%s%s",s1,s2);
	n=strlen(s1),m=strlen(s2);
	rep(i,0,n-1) a[i].x=(double)(s1[n-i-1]-'0');
	rep(i,0,m-1) b[i].x=(double)(s2[m-i-1]-'0');
	now=1;//单位根中的k值，默认为2的自然数次幂 
	while(now<=n+m) now<<=1,++k;
	rep(i,0,now-1)
	 f[i]=(f[i>>1]>>1)|((i&1)<<(k-1));//背板子做笔记 ！！！ 
	FFT(a,1);
	FFT(b,1);
	rep(i,0,now) a[i]=a[i]*b[i];
	FFT(a,-1);
	rep(i,0,now)
	{
		ans[i]+=(ll)(a[i].x/now+0.49);
		if(ans[i]>=10)
		{
			ans[i+1]+=(ans[i]/10),ans[i]%=10;
			if(i==now) ++now;
		}
	}
	while(ans[now]==0&&now>=1) --now;
	per(i,now,0) putchar(ans[i]+'0');
	return 0;
}