(1 + 2x) * (3 + 4x) = 1×3 + 1×4x + 2x×3 + 2x×4x
                     = 3 + 4x + 6x + 8x²
                     = 3 + 10x + 8x²

(1 + 2x + 3x² + ... + 1000x⁹⁹⁹) * (2 + 4x + 6x² + ... + 2000x⁹⁹⁹)

#include <iostream>
#include <complex>   // 复数类型
#include <vector>    // 动态数组
#include <cmath>     // 数学函数
using namespace std;

typedef complex<double> cd;  // 复数类型别名，double精度
const double PI = acos(-1);  // 圆周率π

// 快速傅里叶变换（FFT）
// a: 输入的多项式系数（用复数表示），长度必须是2的幂
// invert: false表示正向变换（系数→点值），true表示反向变换（点值→系数）
void fft(vector<cd>& a, bool invert) {
    int n = a.size();   // 长度

    // 第一步：将系数重新排列（位逆序置换），相当于分治的“拆开”
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;   // 从最高位开始
        for (; j & bit; bit >>= 1) j ^= bit;  // 找下一个逆序位置
        j ^= bit;
        if (i < j) swap(a[i], a[j]);  // 交换位置
    }

    // 第二步：迭代合并，len是当前合并的小段长度（2,4,8,...）
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);  // 旋转因子的角度
        cd wlen(cos(ang), sin(ang));  // 长度为len的旋转因子
        for (int i = 0; i < n; i += len) {  // 每段len个元素
            cd w(1);  // 当前旋转因子，初始为1
            for (int j = 0; j < len/2; j++) {
                cd u = a[i+j];                   // 左半部分
                cd v = a[i+j+len/2] * w;         // 右半部分乘旋转因子
                a[i+j] = u + v;                  // 合并后的左半
                a[i+j+len/2] = u - v;            // 合并后的右半
                w *= wlen;                       // 更新旋转因子
            }
        }
    }

    // 如果是反向变换，要把每个数除以n（恢复原来的系数）
    if (invert) for (cd &x : a) x /= n;
}

// 两个整数系数的多项式乘法，返回结果系数向量
vector<int> multiply(vector<int>& a, vector<int>& b) {
    // 把整数系数转为复数系数
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    // 找到大于等于a+b长度的最小2的幂（FFT要求长度是2的幂）
    while (n < a.size() + b.size()) n <<= 1;
    fa.resize(n);   // 补0到长度n
    fb.resize(n);

    // 正向变换（系数→点值）
    fft(fa, false);
    fft(fb, false);

    // 点值乘法：对应位置相乘
    for (int i = 0; i < n; i++) fa[i] *= fb[i];

    // 反向变换（点值→系数）
    fft(fa, true);

    // 将复数结果取整并转成整数
    vector<int> result(n);
    for (int i = 0; i < n; i++) result[i] = round(fa[i].real());
    return result;
}

int main() {
    vector<int> a = {1, 2}; // 表示多项式 1 + 2x
    vector<int> b = {3, 4}; // 表示多项式 3 + 4x
    auto res = multiply(a, b);  // 调用乘法
    // 输出结果：3 10 8 对应 3 + 10x + 8x²
    for (int x : res) cout << x << " ";
    return 0;
}

int main() {
    vector<int> a = {1, 2, 3}; // 1 + 2x + 3x²
    vector<int> b = {4, 5};    // 4 + 5x
    auto res = multiply(a, b);
    // 期望结果：4*1=4, 1*5+2*4=5+8=13, 2*5+3*4=10+12=22, 3*5=15
    // 即：4 + 13x + 22x² + 15x³
    for (int x : res) cout << x << " ";  // 输出：4 13 22 15 0
    return 0;
}