FFT，迭代+蝴蝶变换，只是用了 std::complex，至于全T吗？

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
#define F(i,a,b) for(int i = a; i < b; i++)
typedef long double ld;
typedef complex<ld> cp;
const cp pi(3.1415926535897932L, 0.0L);
const cp ci(0.0L, 1.0L); cp u, t;
int ans[N], bit = 0, rev[N];
void FFT(cp* a, int n, int f) {
	if (n == 1)return;
	for (int i = 0; i < n; i++)if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int mid = 1; mid < n; mid <<= 1) {
		cp wn(cos(pi / (ld)mid) + (ld)f * ci * sin(pi / (ld)mid));
		for (int i = 0; i < n; i += (mid << 1)) {
			cp w(1.0L, 0.0L);
			for(int j = 0; j < mid; j++){
				u = a[i + j], t = w * a[i + j + mid];
				a[i + j] = u + t, a[i + j + mid] = u - t;
				w = w * wn;
			}
		}
	}
}
cp a[N], c[N]; int n;
void work() {
	FFT(a, n, 1), FFT(c, n, 1);
	F(i, 0, n)a[i] *= c[i];
	FFT(a, n, -1);
	F(i, 0, n)ans[i] = int(a[i].real() / (ld)n + 0.1L);
	F(i, 0, n)ans[i + 1] += ans[i] / 10, ans[i] = ans[i] % 10;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(); cout.tie();
	string s1, s2;
	cin >> s1 >> s2;
	F(i, 0, s1.size())a[i] = ld(s1[s1.size() - i - 1] - '0');
	F(i, 0, s2.size())c[i] = ld(s2[s2.size() - i - 1] - '0');
	n = 1; int len = max(s1.size(), s2.size());
	while (n <= len)n <<= 1, ++bit; n <<= 1, ++bit;
	F(i, 0, n)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1)); work();
	while (ans[len] == 0 && len)--len;
	for (int i = len; i >= 0; i--)cout << ans[i];
	return 0;
}

提交记录