多项式乘法
给定一个次多项式和次多项式，求出与的卷积。

# 输入格式

第一行两个整数。
接下来一行个数字，从低到高表示的系数。
接下来一行个数字，从低到高表示的系数。

# 输出格式

一行个数字，从低到高表示的系数。

# 输入输出样例

# 输入样例

1 2
1 2
1 2 1

# 输出样例

1 4 5 2

# 问题分析

假设两个多项式和，两个多项式可以写作：

传统方法是利用两个多项式的系数进行卷积运算，得到一个次多项式：

这种卷积运算的时间复杂度为，显然在数据范围较大的情况下难以承受，而利用快速傅里叶变换可将时间复杂度降为。

# FFT介绍

快速傅里叶变换 (fast Fourier transform),即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
FFT（Fast Fourier Transformation） 是离散傅氏变换（DFT）的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。
——百度百科

要解决的问题是多项式的乘法，而一个多项式的表示方法并不唯一，传统意义上多项式的表示利用的是系数表示法，即对于一个多项式可由一个系数向量唯一表示。

而除了系数表示法之外，多项式也可以利用点值表示，对于多项式，选定个值带入多项式进行计算，得到个点值)这个点值也可唯一表示多项式。

因此当我们利用同一个向量得到了两个两个多项式的点值表示法后，用对应点值相乘，得到即为两个多项式的乘积多项式的点值表示，这个过程的时间复杂度为。

需要注意的一点是，当两个多项式次数为时，他们的乘积多项式次数为，因此利用点值表示计算时，计算两个多项式的点值表示时应选用个变量，才能使得到的结果唯一表示乘积多项式。

然而对于一个多项式来说，代入任意选定的变量计算他的点值表示法时间复杂度依然是，并没有起到优化的效果，而快速傅里叶变换解决了这个问题，使得系数表示法转化为点值表示法的时间复杂度降低为。

# 快速傅里叶变换FFT

FFT在计算多项式的系数表示法变换为点值表示法时，选定复平面上单位圆上的单位复根作为变量计算多项式的点值，在这里单位根满足以下的一些性质（如果有不理解的可以自行查阅复数的一些相关知识)：

图1 FFT

以上的这些性质都可以由Euler公式得到，推导过程并非FFT重点这里就省略了。

对于一个多项式，我们可以对其进行划分，将偶数次项与奇数次项分开，在这里假设为奇数，得到：

我们分别定义两个多项式：

那么原多项式就可以表示为：

将代入上式：

将代入上式：

由此可以发现，和在计算的过程中只有一个符号不同，因此在进行枚举计算时即可直接得到的值，利用这种方法进行分治，便可以将复杂度降至。

# 逆傅里叶变换IFFT

利用上述的方法得到了乘积多项式的点值表示法，那么现在需要解决的问题时如何将点值表示法再转换回系数表示法。

假设得到多项式的FFT点值表示为，其系数表示为，根据FFT原理，可如下表示：

取的共轭复数，如下定义向量：

那么由定义可以推导出如下的公式：

图2 FFT

对于复平面上的单位根，有如下的性质：

因此可以得到：

因此，利用FFT得到了多项式的点值表示后只需要将变量换为原本选定的单位根的共轭复数再进行一次FFT就能得到多项式的系数表示。

这里需要说明一个问题，我们以上的讨论都是建立在**为的幂次的条件下的，那么当不是的幂次时需要将扩大为大于的最小的的幂次**，在进行逆傅里叶变换时，通过上述的推导可以发现，当我们计算的中的值大于原本的时，就不存在的情况了，因此求得的为，表示该多项式的次项系数为。

# 但是问题到这里并没有结束

当有的毒瘤数据范围非常大的时候，用递归进行计算时，大量的递归会造成栈溢出，那么是否有不用递归的做法？

# FFT的迭代实现

对于这样一个序列，我们观察对其进行二分的过程：

图3 FFT迭代

我们发现了一个神奇的性质，在对这个序列进行二分以后的序列的二进制可以由原序列的二进制进行翻转得到，那么我们可以利用这个性质，用一个的方法可以直接得到最终的序列，从而省去了递归的过程，用最终的序列反向递推实现即可。

# Rader算法

Rader算法即为实现上述操作的一种算法，对于个数，我们把递增自然数称为顺序数列；对顺序数列中的每一个数，将其二进制倒序后转化为十进制，称为倒序数列。
对于一个顺序数列，第个数的二进制可以视为将第（这里是整除）个数的二进制左移一位，再根据的奇偶性对其末尾加或者不加。
那么要得到它的倒序数列，只需要将这个操作反向进行即可，即第个数的二进制可以视为将第个数的二进制右移一位，再根据的奇偶性对其最高加或者不加，这里最高位即为第位。

# 迭代进行FFT（蝴蝶变换）

利用Rader算法求得了递推序列，那么如何通过迭代得到最终的答案？
这其实跟迭代实现01背包的做法思路差不多，对于求在次单位根的各幂次的点值时，次单位根的各幂次在或处的点值已经被计算并且储存在了数组中，那么在下一层的迭代过程中直接使用数组存储的答案继续进行迭代计算即可。

# 迭代优化FFT代码实现

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

using namespace std;

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

int n, m;
struct Complex
{
    double x, 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};
    }
    Complex operator* (const Complex& t) const
    {
        return {x * t.x - y * t.y, x * t.y + y * t.x};
    }
}a[N], b[N];
int rev[N], bit, tot;

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)
    {
        auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
        for (int i = 0; i < tot; i += mid * 2)
        {
            auto wk = Complex({1, 0});
            for (int j = 0; j < mid; j ++, wk = wk * w1)
            {
                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;
    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;
}