我的 FFT T 了
  • 板块灌水区
  • 楼主Xia_Qian
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/6 22:27
  • 上次更新2024/1/7 10:21:15
查看原帖
我的 FFT T 了
925044
Xia_Qian楼主2024/1/6 22:27
#include <bits/extc++.h>

const int MAXN = 1e7 + 10;

const double Pi = acos(-1.0);

struct complex {
    double x, y;

    explicit complex(double xx = 0, double yy = 0) : x(xx), y(yy) {}
} a[MAXN], b[MAXN];

complex operator+(complex lhs, complex rhs) { return complex{lhs.x + rhs.x, lhs.y + rhs.y}; }

complex operator-(complex lhs, complex rhs) { return complex{lhs.x - rhs.x, lhs.y - rhs.y}; }

complex operator*(complex lhs, complex rhs) {
    return complex{lhs.x * rhs.x - lhs.y * rhs.y, lhs.x * rhs.y + lhs.y * rhs.x};
}

int l, r[MAXN];
int limit = 1;

void FFT(complex *A, int type) {
    for (int i = 0; i < limit; i++) {
        if (i < r[i]) {
            std::swap(A[i], A[r[i]]);
        }
    }
    for (int mid = 1; mid < limit; mid <<= 1) {
        complex Wn(cos(Pi / mid), type * sin(Pi / mid));
        for (int R = mid << 1, j = 0; j < limit; j += R) {
            complex w(1, 0);
            for (int k = 0; k < mid; k++, w = w * Wn) {
                complex x = A[j + k], y = w * A[j + mid + k];
                A[j + k] = x + y;
                A[j + mid + k] = x - y;
            }
        }
    }
}

int main() {
    int N, M;
    std::cin >> N >> M;
    for (int i = 0; i <= N; i++) {
        std::cin >> a[i].x;
    }
    for (int i = 0; i <= M; i++) {
        std::cin >> b[i].x;
    }
    while (limit <= N + M) {
        limit <<= 1;
        l++;
    }
    for (int i = 0; i < limit; i++) {
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    }
    FFT(a, 1);
    FFT(b, 1);
    for (int i = 0; i <= limit; i++) {
        a[i] = a[i] * b[i];
    }
    FFT(a, -1);
    for (int i = 0; i <= N + M; i++) {
        std::cout << static_cast<int>(std::round(a[i].x / limit)) << " ";
    }
    return 0;
}
2024/1/6 22:27
加载中...