题解-SP235

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题面大意

计算 $T$ 组高精度的乘积。

解题思路

本题目无法使用普通高精度通过。

不过我们这样考虑，假如我们计算 $13 \times 140$，我们可以这样思考：

将其每一项的系数提取出来，就是我们的结果了。

然后我们看看这个式子，这不就是多项式卷积的模板吗？

所以使用 FFT 优化高精乘，通过此题。

#include<stdio.h>
#include<complex>
#include<string.h>

#define maxn 8000007

std::complex<double> a[maxn],b[maxn];
const double pi = 3.1415926535897932;

int n,m,tmp,len=1;

void fft(std::complex<double> *c,int len,int op){
	if(len==1)
		return;
	std::complex<double> even[len>>1],odd[len>>1];
	for(int i=0;i<len;i+=2)
		even[i>>1]=c[i],
		odd [i>>1]=c[i+1];
	fft(even,len>>1,op);
	fft(odd ,len>>1,op);
	std::complex<double> unit_root(cos(2*pi/len),sin(2*pi/len)*op) , c1(1,0);
	for(int i=0;i<(len>>1);i++,c1*=unit_root)
		c[i] =          even[i]+c1*odd[i],
		c[i+(len>>1)] = even[i]-c1*odd[i];
}

char s1[maxn],s2[maxn];
int rs[maxn];
int T;

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s%s",s1,s2);
		n = strlen(s1);
		m = strlen(s2);
		for(int i=0;i<n;i++)
			a[n-i-1].real(s1[i]^'0');
		for(int j=0;j<m;j++)
			b[m-j-1].real(s2[j]^'0');

		while(len < n+m+1)
			len<<=1;

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

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

		fft(a,len,-1);

		for (int i=0;i<=n+m+1;i++)
	        rs[i] = int(a[i].real()/len+0.01);

	    for (int i=0;i<=n+m+1;i++)
	    	rs[i+1] += rs[i]/10,
	    	rs[i]%=10;

		int qd0=1;
	    for (int i=n+m+1;i>=0;i--){
	    	if(rs[i]==0 && qd0)continue;
	    	qd0=0;
	    	printf("%d",rs[i]);
		}
		puts("");

		for(int i=0;i<len;i++)
			a[i]=0,b[i]=0;
	}
	return 0;
}