洛谷 P3803 【模板】多项式乘法（FFT）

Description:

这是一道FFT模板题

注意：虽然本题开到3s，但是建议程序在1s内可以跑完，本题需要一定程度的常数优化。

给定一个n次多项式F(x)，和一个m次多项式G(x)。

请求出F(x)和G(x)的卷积。

Input:

一行2个正整数n,m。

接下来一行n+1个数字，从低到高表示F(x)的系数。

接下来一行m+1个数字，从低到高表示G(x))的系数。

保证输入中的系数大于等于 0 且小于等于9。

对于100%的数据： $n,m\le {10}^6,$n,m≤106, 共计20个数据点，2s。

数据有一定梯度。

空间限制：256MB

Output:

一行n+m+1个数字，从低到高表示F(x)∗G(x)的系数。

Sample Input:

1 2
1 2
1 2 1

Sample Output:

1 4 5 2

题目链接

快速傅里叶变换（FFT）模板题。

推荐两篇FFT详解博客:

傅里叶变换(FFT)学习笔记

FFT·快速傅里叶变换

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e6 + 5;
const double pi = acos(-1.0);

struct Complex {
    double X, Y;

    Complex operator + (const Complex &B) const {
        return Complex {X + B.X, Y + B.Y};
    }

    Complex operator - (const Complex &B) const {
        return Complex {X - B.X, Y - B.Y};
    }

    Complex operator * (const Complex &B) const {
        return Complex {X * B.X - Y * B.Y, X * B.Y + Y * B.X};
    }
    
    Complex operator / (const Complex &B) const {
        double Temp = B.X * B.X + B.Y * B.Y;
        return Complex {(X * B.X + Y * B.Y) / Temp, (Y * B.X - X * B.Y) / Temp};
    }
};

int N, M;
int L;
int Limit;
int R[maxn];

void FFT(Complex F[], int Op) {
    for (int i = 0; i < Limit; ++i) {
        if (i < R[i]) {
            swap(F[i], F[R[i]]);
        }
    }
    for (int j = 1; j < Limit; j <<= 1) {
        Complex Temp = Complex {cos(pi / j), Op * sin(pi / j)};
        for (int k = 0; k < Limit; k += (j << 1)) {
            Complex Buffer = Complex {1.0, 0.0};
            for (int l = 0; l < j; ++l) {
                Complex Tx = F[k + l], Ty = Buffer * F[k + j + l];
                F[k + l] = Tx + Ty;
                F[k + j + l] = Tx - Ty;
                Buffer = Buffer * Temp;
            }
        }
    }
}

Complex A[maxn], B[maxn];

void Cal() {
    Limit = 1; L = 0;
    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);
}

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &M);
    for (int i = 0; i <= N; ++i) {
        scanf("%lf", &A[i].X);
    }
    for (int i = 0; i <= M; ++i) {
        scanf("%lf", &B[i].X);
    }
    Cal();
    for (int i = 0; i <= N + M; ++i) {
        printf("%.0lf ", fabs(A[i].X / Limit));
    }
    return 0;
}