#include <iostream>
#include <complex>
#include <vector>
#include <cmath>
using namespace std;

using Complex = complex<double>;       // 复数类型
const double PI = acos(-1.0);          // 圆周率

// 递归FFT，a是系数向量，长度n必须为2的幂
// invert = false 表示 DFT（正变换），true 表示 IDFT（逆变换）
void fft(vector<Complex>& a, bool invert) {
    int n = a.size();                  // 当前长度
    if (n == 1) return;                // 只有一个点，递归结束

    // 分成奇偶两部分
    vector<Complex> a0(n / 2), a1(n / 2);
    for (int i = 0; i < n / 2; ++i) {
        a0[i] = a[2 * i];              // 偶数下标：a0, a2, a4...
        a1[i] = a[2 * i + 1];          // 奇数下标：a1, a3, a5...
    }

    // 递归计算两个子多项式在 n/2 个单位根上的值
    fft(a0, invert);
    fft(a1, invert);

    // 当前层蝶形操作
    double angle = 2 * PI / n * (invert ? -1 : 1); // 正变换角度为正，逆变换为负
    Complex w(1, 0);                               // w = omega_n^0 = 1
    Complex wn(cos(angle), sin(angle));            // 步长因子 omega_n^1

    for (int i = 0; i < n / 2; ++i) {
        Complex t = w * a1[i];                     // 乘上旋转因子
        a[i] = a0[i] + t;                         // 上半部分
        a[i + n / 2] = a0[i] - t;                 // 下半部分
        w *= wn;                                  // w 更新为下一个 omega_n^k
    }
}

// 使用FFT进行两个整数多项式乘法
// a, b 是系数向量（低次到高次）
vector<long long> multiplyPolynomialsFFT(const vector<int>& a, const vector<int>& b) {
    // 1. 补成长度，找到大于等于目标长度的2的幂
    int n = 1;
    while (n < a.size() + b.size() - 1) n <<= 1;

    // 2. 复制到复数向量
    vector<Complex> fa(n, 0), fb(n, 0);
    for (size_t i = 0; i < a.size(); ++i) fa[i] = Complex(a[i], 0);
    for (size_t i = 0; i < b.size(); ++i) fb[i] = Complex(b[i], 0);

    // 3. DFT：将系数转化为点值
    fft(fa, false);
    fft(fb, false);

    // 4. 点乘：对应位置复数相乘（就是函数值相乘）
    for (int i = 0; i < n; ++i) fa[i] *= fb[i];

    // 5. IDFT：将点值转回系数
    fft(fa, true);

    // 6. 除以 n 并四舍五入取整（因为IDFT公式要除以n）
    vector<long long> result(n);
    for (int i = 0; i < n; ++i) {
        result[i] = llround(fa[i].real() / n);  // 四舍五入，消除微小浮点误差
    }

    // 7. 去掉尾部多余的0（如果乘积最高次系数为0）
    while (result.size() > 1 && result.back() == 0) result.pop_back();
    return result;
}

int main() {
    // 例子：A(x) = 1 + 2x + 3x^2，B(x) = 5 + 4x
    vector<int> A = {1, 2, 3};
    vector<int> B = {5, 4};

    auto prod = multiplyPolynomialsFFT(A, B);
    cout << "A * B = ";
    // 从高次到低次输出
    for (int i = prod.size() - 1; i >= 0; --i) {
        cout << prod[i] << (i > 0 ? " " : "");
    }
    cout << endl;
    // 输出应该是：12 23 10 5 （对应 12x^3 + 23x^2 + 10x + 5）
    return 0;
}

import cmath
import math

def fft(a, invert):
    """
    递归FFT
    a: 复数列表，长度必须为2的幂
    invert: False表示DFT，True表示IDFT
    """
    n = len(a)
    if n == 1:
        return

    # 分奇偶
    a0 = [a[i] for i in range(0, n, 2)]
    a1 = [a[i] for i in range(1, n, 2)]

    # 递归
    fft(a0, invert)
    fft(a1, invert)

    angle = 2 * math.pi / n * (-1 if invert else 1)
    wn = complex(math.cos(angle), math.sin(angle))
    w = complex(1, 0)

    for i in range(n // 2):
        t = w * a1[i]                # 乘旋转因子
        a[i] = a0[i] + t
        a[i + n // 2] = a0[i] - t
        w *= wn

def multiply_polynomials_fft(a, b):
    """使用FFT进行整数多项式乘法"""
    # 补成长度（2的幂）
    n = 1
    while n < len(a) + len(b) - 1:
        n <<= 1

    # 创建复数向量，后面补0
    fa = [complex(x, 0) for x in a] + [complex(0, 0)] * (n - len(a))
    fb = [complex(x, 0) for x in b] + [complex(0, 0)] * (n - len(b))

    # DFT
    fft(fa, False)
    fft(fb, False)

    # 点乘
    for i in range(n):
        fa[i] *= fb[i]

    # IDFT
    fft(fa, True)

    # 除以n并四舍五入
    result = [round(fa[i].real / n) for i in range(n)]
    # 去掉尾部多余0
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    return result

# 测试
A = [1, 2, 3]   # 3x^2 + 2x + 1
B = [5, 4]      # 4x + 5
prod = multiply_polynomials_fft(A, B)
print("A * B =", prod[::-1])   # 反转显示：高次在前