既然是第一篇题解，那一定就要足够的炫酷。。。

FFT（Fast Fourier Transformation），中文名快速傅里叶变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。
朴素高精度乘法的时间为O(n^2)，但FFT只需O(nlog^2n)
核心在于系数与点值的转换。
接下来就是模板了。
最好手写complex…

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define pi acos(-1.0)
using namespace std;
int getint() {
	int ret=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9') {
		ret=ret*10+(int)(ch-'0');
		ch=getchar();
	}
	return ret;
}
struct complex {
	double r,i;
	complex(double real=0.0,double image=0.0) {
		r=real;
		i=image;
	}
	complex operator +(const complex o) {
		return complex(r+o.r,i+o.i);
	}
	complex operator -(const complex o) {
		return complex(r-o.r,i-o.i);
	}
	complex operator *(const complex o) {
		return complex(r*o.r-i*o.i,r*o.i+i*o.r);
	}
} x1[200005],x2[200005];
char a[200005/2],b[200005/2];
int sum[200005];
void brc(complex *...