「FFT/NTT」「多项式」 | 落影汐雾的x号虚空印刷站

Update on A.D.2019-08-15

必忘原理的FFT

测试一下视频，然而貌似只有bilibili的外链比较好总不能放Youtube？，然而鬼畜的二维码与顶部链接比前几年在mcbbs看的时候烂多了。

---

在2019年8月15日，终于看懂了FFT的推导过程。

首先是FFT的板子，这个写法其实很优美记不住的。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <complex>
#define R register

using namespace std;
const int N = 4.2e6;
const double PI = acos(-1);
int n, r[N];
class C {
public:
    double r, i;
    C() { r = i = 0; }
    C(R double x, R double y) { r = x; i = y; }
    C operator + (R C& x) { return C(r+x.r, i+x.i); }
    C operator - (R C& x) { return C(r-x.r, i-x.i); }
    C operator * (R C& x) { return C(r*x.r-i*x.i, r*x.i+i*x.r); }
    void operator += (R C& x) { r += x.r; i += x.i; }
    void operator *= (R C& x) { R double t = r; r = r*x.r-i*x.i; i = t*x.i+i*x.r; }
}f[N], g[N];
inline void FFT(R C *a, R int op)
{
    R C W, w, t, *a0, *a1;
    R int i, j, k;
    for (i = 0; i < n; ++i)
        if (i < r[i]) t = a[i], a[i] = a[r[i]], a[r[i]] = t;
    for(i = 1; i < n; i <<= 1)
        for(W = C(cos(PI/i), sin(PI/i) * op), j = 0; j < n; j += i << 1)
            for(w = C(1, 0), a1 = i + (a0 = a + j), k = 0; k < i; ++k, ++a0, ++a1, w*=W)
                t = *a1 * w, *a1 = *a0 - t, *a0 += t;
}
int main()
{
    R int m, i, l = 0;
    scanf("%d%d", &n, &m);
    for(i = 0; i <= n; i++) scanf("%lf", &f[i].r);
    for(i = 0; i <= m; i++) scanf("%lf", &g[i].r);
    for(m += n, n = 1; n <= m; n <<= 1, ++l);
    for(i = 0; i < n; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    FFT(f, 1); FFT(g, 1);
    for(i = 0; i < n; ++i) f[i] *= g[i];
    FFT(f, -1);
    for(i = 0; i <= m; ++i) printf("%.0lf ", fabs(f[i].r) / n);
    return 0;
}

咕，马上补.

本文由 落影汐雾 原创，采用 保留署名-非商业性使用-禁止演绎 4.0-国际许可协议
本文链接：https://x.lyxw.xyz/2019/FFT/