题目描述
题解
OI中最恶心的两件事：常系数齐次线性递推（手玩多项式除法）和低进制卷积（手玩转移矩阵和求其逆矩阵）
考虑构造三进制下不进位加法的卷积
也就是构造映射 $f$，满足对于每一列有 $x_ix_j=x_{i \oplus j}$
同时要求每一列的 $x_i$，应该是 $\omega_{\tau_i}^{\lambda_{i,j}}$
首先有：
$$
\begin{cases}
\tau_0=1 \\
\tau_1=3 \\
\tau_2=3 \\
\end{cases}
$$
即 $f$ 实际上是：
$$
\begin{pmatrix}
1 & \omega_3^{y_0} & \omega_3^{z_0} \\
1 & \omega_3^{y_1} & \omega_3^{z_1} \\
1 & \omega_3^{y_2} & \omega_3^{z_2} \\
\end{pmatrix}
$$
需要满足：
$$
\begin{cases}
y_0+y_0=y_0 \\
y_0+y_1=y_1 \\
y_0+y_2=y_2 \\
y_1+y_1=y_2 \\
y_1+y_2=y_0 \\
y_2+y_2=y_1
\end{cases}
$$
显然 $z$ 和 $y$ 的情况是一样的，同时要求列向量线性无关，那么一组合法解就是：
$$
\begin{pmatrix}
1 & 1 & 1 \\
1 & \omega_3 & \omega_3^{2} \\
1 & \omega_3^{2} & \omega_3 \\
\end{pmatrix}
$$
同时有等式 $\omega_3^2+\omega+1=0$
那么可以扩域到 $\mathbb{Z}[\omega]$，也就是用 $a+b\omega$ 来表示所有的数
考虑求这个矩阵的逆矩阵，通过单位根横等式，有：
$$
\begin{pmatrix}
1 & 1 & 1 \\
1 & \omega_3 & \omega_3^{2} \\
1 & \omega_3^{2} & \omega_3 \\
\end{pmatrix}
\begin{pmatrix}
1 & 1 & 1 \\
1 & \omega_3^2 & \omega_3 \\
1 & \omega_3 & \omega_3^2 \\
\end{pmatrix}
=
3
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{pmatrix}
$$
那么逆矩阵就是：
$$
\frac{1}{3}
\begin{pmatrix}
1 & 1 & 1 \\
1 & \omega_3^2 & \omega_3 \\
1 & \omega_3 & \omega_3^2 \\
\end{pmatrix}
$$
