定义

定义循环矩阵为：

$$
\begin{pmatrix} a _ {0} & a _ {1} & a _ {2} & \cdots & a _ {n-1} \\ a _ {n-1} & a _ {0} & a _ {1} & \cdots & a _ {n-2} \\ a _ {n-2} & a _ {n-1} & a _ {0} & \cdots & a _ {n-3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a _ {1} & a _ {2} & a _ {3}& \cdots & a _ {0} \end{pmatrix}
$$

换而言之，$A _ {i,j}=A _ {0,(j-i) \bmod n}$，也就是说可以用循环矩阵的第一行来表示整个矩阵

矩阵乘法 $O(k^3)$

根据矩阵乘法的定义，假设有 $A,B$ 两个 $n$ 阶矩阵，则 $C = A \times B$ 为：

$$
c _ {i,j}=\sum _ {k=0}^{n-1}a _ {i,k}b _ {k,j}
$$

矩阵乘法 $O(k^2)$

考虑循环矩阵的特殊性，即可以用第一行来表示整个矩阵，也就是说这个矩阵的所有信息只存在于第一行中

那么考虑 $n$ 阶矩阵 $C=A \times B$：

$$
\begin{aligned}
c _ {i,j}
&=\sum _ {k=0}^{n-1}a _ {i,k}b _ {k,j} \\
&=\sum _ {k=0}^{n-1}a _ {0,(k-i) \bmod n}b _ {0,(j-k) \bmod n} \\
&=c _ {0,(j-i) \bmod n} \\
\end{aligned}
$$

也就是说，循环矩阵的乘积依旧是循环矩阵

所以可以得知，循环矩阵的乘法实际上只有第一行参与了运算，那么就可以直接用 $a _ 0,b _ 0,c _ 0$ 代替掉 $A,B,C$ 了

于是可以得到：

$$
c _ {k}=\sum _ {i+j \equiv k \pmod {n}}a _ {i}b _ {j}
$$

矩阵乘法 $O(k \log k)$

实际上 $C=A \times B$ 是一个循环卷积运算，直接求出 $c’=a \times b$，然后可以得到：

$$
c _ i=c’ _ i+c’ _ {i+n}
$$

应用

给定一个序列 $p _ 0 \sim p _ {n-1}$，以及一个系数系列 $t _ 0 \sim t _ {n-1}$，一共进行 $T$ 次变换，每一次会把 $p$ 变化为 $p’$，其中：

$$
p _ i’=\sum _ {j=0}^{n-1}t _ {(j-i) \bmod n}p _ j
$$

是不是感觉有点眼熟？我们来看一下常系数齐次线性递推的一般形式：
$$
p _ i=\sum _ {j=1}^{k}t _ jp _ {i-j}
$$

没错，本质上是模意义下的常系数齐次线性递推！

构造矩阵 $A$：

$$
A=
\begin{pmatrix}
p _ 0 & p _ 1 & \cdots & p _ {n-1} \\
\end{pmatrix}
$$

构造矩阵 $B$：

$$
B=
\begin{pmatrix}
t _ {0} & t _ {n-1} & \cdots & t _ {1} \\
t _ {1} & t _ {0} & \cdots & t _ {2} \\
\vdots & \vdots & \ddots & \vdots \\
t _ {n-1} & t _ {n-2} & \cdots & t _ {0} \\
\end{pmatrix}
$$

那么矩阵 $B$ 依然是一个循环矩阵，但是需要把 $t _ 1 \sim t _ {n-1}$ 翻转一下

之后可以得到矩阵 $C=A \times B$：

$$
C=
\begin{pmatrix}
p’ _ 0 & p’ _ 1 & \cdots & p’ _ {n-1} \\
\end{pmatrix}
$$

然而行矩阵乘以循环矩阵还需要再进行讨论，不妨直接把 $A$ 扩充为循环矩阵，最后第一行的结果依旧是期望的结果：

$$
A=
\begin{pmatrix}
p _ 0 & p _ 1 & \cdots & p _ {n-1} \\
p _ {n-1} & p _ 0 & \cdots & p _ {n-2} \\
\vdots & \vdots & \ddots & \vdots \\
p _ {1} & p _ {2} & \cdots & p _ {0} \\
\end{pmatrix}
$$

即 $C=A \times B$ 就是：

$$
C=
\begin{pmatrix}
p’ _ 0 & p’ _ 1 & \cdots & p’ _ {n-1} \\
p’ _ {n-1} & p’ _ 0 & \cdots & p’ _ {n-2} \\
\vdots & \vdots & \ddots & \vdots \\
p’ _ {1} & p’ _ {2} & \cdots & p’ _ {0} \\
\end{pmatrix}
$$

模 $2$ 意义下的多项式的平方

$$
\begin{aligned}
& (a _ 1+a _ 2+\cdots+a _ n)^2 \\
=& a _ 1^2+a _ 2^2+\cdots+a _ n^2+2\left(\sum _ {i=1}^{n}a _ i\sum _ {j=i+1}^{n}a _ j\right)
\end{aligned}
$$

那么在模 $2$ 意义下，就是：

$$
\left(\sum _ {i=0}^{n}a _ ix^i\right)^2 \equiv \sum _ {i=0}^{n}a _ i^2x^{2i} \pmod {2}
$$