题目描述

太长了,略

题解

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}
$$