終于動(dòng)手寫完了FFT.. (wKw)
原題
#include <iostream>
#include<complex>
#include<cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef complex<double> cp;
const int maxn = 1000007;
const double PI = acos(-1);
char s1[maxn], s2[maxn];
cp omg[maxn], inv[maxn],a[maxn],b[maxn];
int res[maxn];
int n=1;
void init() {//預(yù)處理
for (int i = 0; i < n; i++) {
omg[i] = cp(cos(2 * PI * i / n), sin(2 * PI * i / n));
inv[i] = conj(omg[i]);//模為1時(shí)，倒數(shù)和共軛復(fù)數(shù)相同
}
}
void FFT(cp *a,cp *omg) {
int lim = 0;
while ((1 << lim) < n)lim++;
for (int i = 0; i < n; i++) {
int t = 0;
for (int j = 0; j < lim; j++)
if ((i >> j) & 1) t |= (1 << (lim - j - 1));
if (i < t)swap(a[i], a[t]);
}
for (int l = 2; l <= n; l*=2) {
int m = l/2;
for (cp *p = a; p != a + n; p+=l) {
for (int i = 0; i < m; i++) {
cp t = omg[n / l * i] * p[i + m];//蝴蝶優(yōu)化
p[i + m] =p[i]- t;
p[i] += t;
}
}
}
}
int main()
{
int tmp;
scanf("%d", &tmp);
scanf("%s%s", s1, s2);
int lena = strlen(s1), lenb = strlen(s2);
while (n < lena + lenb) n *= 2;
for (int i = 0; i < lena; i++)
a[i].real(s1[lena - 1 - i] - '0');
for (int i = 0; i < lenb; i++)
b[i].real(s2[lenb - 1 - i] - '0');
init();
FFT(a, omg);
FFT(b, omg);
for (int i = 0; i < n; i++)
a[i] *= b[i];
FFT(a, inv);
for (int i = 0; i < n; i++) {
res[i] += floor(a[i].real() / n + 0.5);
res[i + 1] += res[i] / 10;
res[i] %= 10;
}
int i = lena + lenb - 1; //為了對(duì)付一組奇怪的數(shù)據(jù)，計(jì)算結(jié)果開(kāi)頭有四個(gè)零
while (!res[i])i--;
for (; i >= 0; i--)
putchar('0' + res[i]);
return 0;
}
