引入问题
什么是多项式卷积
假设我们现在有多项式 $f(x)$ 和 $g(x)$ ,它可以被表示为
$$
f(x)=\sum_{i=0}^{n-1} a_i\cdot x^i\\
g(x)=\sum_{i=0}^{m-1} b_i\cdot x^i
$$
其中 $a$ 和 $b$ 为系数数组, $n$ 和 $m$ 分别为两个多项式的长度
那么它们的卷积为
$$
f(x)\bigotimes g(x)=\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i\cdot b_j\cdot x^{i+j}
$$
也可以表示成
$$
c_k=\sum_{i=0}^ka_i\cdot b_{k-i}
$$
其实就是简单的两个多项式相乘