嘛，本来想写一个单纯的 Poly 学习笔记，但是发现似乎 Poly 及一些其他的代数内容绑定的很深，所以就在此文一起写出了。

多项式简介

定义

在初中阶段我们已经了解了多项式，对于一个求和式 $\sum a_ix^i$，如果是有限项相加，我们就称其为多项式，记为 $F(x)=\sum a_ix^i$。

称一个多项式 $F(x)$ 的度为其最高次项的次数。

运算

多项式的加减法是平凡的，即次数对应的项的系数相加减。这里不过多介绍。核心的操作为多项式的乘法，即给定 $F(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n,G(x)=b_0+b_1x^1+b_2x^2+\cdots+b_mx^m$，我们想要计算 $Q(x)=F(x)\cdot G(x)$，我们有如下公式：

$$Q(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^ma_ix^i\times b_jx^j=\sum\limits_{i=1}^n\sum\limits_{j=1}^m (a_i+b_j)x^{i+j}$$

最终我们会得到一个度为 $n+m$ 的多项式，由于上述算法是 $O(nm)$ 的，我们会在后文介绍一种 $O(n\log n)$ 时间复杂度内解决两个度数为 $n$ 的多项式相乘的算法。

群、群论

定义

定义一个非空集 $G$ 与一种在 $G$ 上的运算 $\oplus$ 构成一个群 $(G,\oplus)$，当且仅当其满足以下条件：

1. 封闭性：对于所有 $x,y\in G$，需要满足 $x\oplus y\in G$。
2. 结合律：对于所有 $x,y,z\in G$，需要满足 $(x\oplus y)\oplus z=x\oplus (y\oplus z)$。
3. 单位元：存在一个单位元 $e$，满足对于所有 $x\in G$，有 $x\oplus e=e\oplus x=x$。
4. 逆元：对于所有 $x\in G$，存在一个 $y\in G$ 满足 $x\oplus y=y\oplus x=e$。

整数集 $\mathbb{Z}$ 与在其上的加法运算 $+$ 构成一个群 $(\mathbb Z,+)$。其中，单位元为 $0$，对于任意数 $x$，其逆元为 $x$ 的相反数。

衍生结构

1. 若结构 $(G,\oplus)$ 满足结合律与封闭性，我们就称其为半群。
2. 若半群 $(G,\oplus )$ 满足单位元，称其为幺半群。
3. 若群 $(G,\oplus)$ 还满足 $\forall x,y\in G,x\oplus y=y\oplus x$，我们称这个群为阿尔贝群。

群上的幂运算

给定一个群 $G$，对于任意的 $g\in G$，设 $e$ 为 $G$ 的单位元，定义 $g^n(n\in \mathbb{N})$ 如下：

1. 当 $n=0$ 时，$g_n=e$。
2. 当 $n>0$ 时，$g_n=g_{n-1}\oplus g$。

对于任意的 $n\in \mathbb{Z}$，定义 $g_n$ 如下：

1. 当 $n\ge 0$ 时，照上文定义。
2. 当 $n<0$ 时，$g_n=(g^{-1})^{-n}$。

幂运算的性质：

1. $g^i\oplus g^j=g^{i+j}$
2. $(g^i)^{-1}=g^{-i}$。
3. $g^i\oplus g^j=g^j\oplus g^i$。

复数

方程 $x^2=-1$ 没有实根，定义 $i^2=-1$，我们就有了 $x_1=i,x_2=-i$ 两个根，此时 $i$ 称为虚数单位。

定义复数为形如 $a+bi$ 的数，其中 $a$ 称为实部，$bi$ 称为虚部。

考虑对于一个数 $x$，如果我们将 $x$ 与 $-1$ 相乘，就相当于在数轴上将其旋转 $180$ 度。我们又有 $i\times i=-1$，所以可以很自然地定义将 $x$ 乘以 $i$ 时，代表将 $x$ 在数轴上逆时针翻转 $90$ 度。

于是我们就将数轴拓展为复平面，其中 $x$ 轴代表实部，$y$ 轴代表虚部。

如图，是复数 $1+i$ 与 $5+2i$ 在复平面上的位置。

复数的运算

复数的加减法是平凡的。对于两个复数 $a+bi$ 与 $c+di$，在复数相加时我们分别将实部与虚部相加，得到 $(a+c)+(b+d)i$，对于减法同理。

快速傅立叶变换 FFT