[bzoj 2179] FFT快速傅立叶

给两个n位十进制正整数x,y, 计算它们的乘积 (不含前导0). (n≤60000) 把低i位的数码看成x^i项的系数, 两个多项式相乘, 令x=10, 即得答案.

但这个 "答案" 不保证每一位是0-9, 无法输出. 所以从低到高手动进位一轮.

typedef complex<double> Complex;
const double pi = acos(-1);
const int N = (1<<17)+1;

namespace Convol {
	int n, rev[N];

	void init(int _n, int s)
	{
		n = _n;
		--s;
		rep (i, 1, n)
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << s);
	}

	void fft(Complex a[], int d=1)
	{
		rep (i, 0, n)
			if (rev[i] < i)
				swap(a[i], a[rev[i]]);
		for (int m = 1; m < n; m <<= 1) {
			Complex _w(cos(pi/m), d*sin(pi/m));
			for (int j = 0; j < n; j += m<<1) {
				Complex w(1);
				rep (k, 0, m) {
					Complex t = w * a[j+m+k];
					a[j+m+k] = a[j+k] - t;
					a[j+k] += t;
					w *= _w;
				}
			}
		}
		if (d == -1)
			rep (i, 0, n) a[i] /= n;
	}

	void convol(Complex x[], int z[])
	{
		static Complex y[N];
		fft(x);
		rep (i, 0, n) {
			int j = (n-i) & (n-1);
			y[i] = Complex(0, 0.25) * (conj(x[j]*x[j]) - x[i]*x[i]);
		}
		fft(y, -1);
		rep (i, 0, n)
			z[i] = round(real(y[i]));
	}
}

using Convol::convol;

Complex a[N];
int b[N];
char str[2][N];

int main()
{
	int n, m = 1, s = 0;
	scanf("%d ", &n);
	fgets(str[0], n+2, stdin);
	fgets(str[1], n+2, stdin);
	while (m < 2*n-1) m <<= 1, ++s;
	Convol::init(m, s);
	rep (i, 0, n) a[n-1-i] = str[0][i] - '0';
	rep (i, 0, n) a[n-1-i] += Complex(0, str[1][i] - '0');
	convol(a, b);
	rep (i, 0, 2*n-1) {
		b[i+1] += b[i] / 10;
		b[i] %= 10;
	}
	int i = 2*n;
	while (i && !b[i]) --i;
	while (i >= 0) putchar('0' + b[i--]);
	putchar('\n');
	return 0;
}