多项式乘法问题

解题思路：

本题是一个裸的多项式乘积问题，$FFT$ 的模板题。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 300010;
const double PI = acos(-1);

struct Complex //复数
{
    double x, y; //x + yi
    Complex operator+(const Complex &t) const //复数减法
    {
        return {x + t.x, y + t.y};
    }
    Complex operator-(const Complex &t) const //复数加法
    {
        return {x - t.x, y - t.y};
    }
    Complex operator*(const Complex &t) const //复数乘法
    {
        return {x * t.x - y * t.y, x * t.y + y * t.x};
    }
}a[N], b[N]; //多项式的点表示法

int n, m;
//rev[i] 表示 i 的二进制翻转后的数，bit 表示二进制有效位数，tot 表示总长度
int rev[N], bit, tot;

//inv 为 1 表示正向变换，系数表示法 -> 点表示法
//inv 为 -1 表示逆向变换，点表示法 -> 系数表示法
void fft(Complex a[], int inv) //快速傅里叶变换
{
    //将序列变成最底层的顺序
    for(int i = 0; i < tot; i++)
        if(i < rev[i]) //只交换一次，否则换过去换回来顺序不变
            swap(a[i], a[rev[i]]);

    for(int mid = 1; mid < tot; mid <<= 1) //当前每段区间长度为 2 * mid，下面一层的区间长度为 mid
    {
        //2 * mid 表示当前区间的长度，即当前的 n
        //如果是正向变换夹角是正的，如果是逆向变换则方向相反，故夹角是负的
        auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
        for(int i = 0; i < tot; i += mid * 2) //枚举当前每段区间的开头
        {
            auto wk = Complex({1, 0}); //k 从 0 开始枚举，w0 = (1, 0)
            for(int j = 0; j < mid; j++, wk = wk * w1) //枚举当前区间中的每一项并计算值
            {
                //A(wk) = A1(wk) +/- wk * A2(wk)
                auto x = a[i + j], y = wk * a[i + j + mid];
                a[i + j] = x + y, a[i + j + mid] = x - y;
            }
        }
    }
}

int main()
{
    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);

    while((1 << bit) < n + m + 1) bit++; //统计有效位数
    tot = 1 << bit; //记录区间总长度

    //预处理 rev
    for(int i = 0; i < tot; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));

    fft(a, 1), fft(b, 1); //正向变换

    for(int i = 0; i < tot; i++) a[i] = a[i] * b[i];

    fft(a, -1); //逆向变换

    for(int i = 0; i <= n + m; i++) printf("%d ", (int)(a[i].x / tot + 0.5)); //将乘积的系数表示法输出

    return 0;
}