基本的なアイデアは公式解説と同じですが、行列を用いて状態を管理する方法を述べます。

それぞれの回転・反転操作によって、マスは次のように移ります。（マスの番号は 0-indexed で考えています）

• 時計回りに \(90\) 度回転 (2 A): \((i, j) \to (j, N - 1 - i)\)
• 反時計回りに \(90\) 度回転 (2 B): \((i, j) \to (N - 1 - j, i)\)
• 上下反転 (3 A): \((i, j) \to (N - 1 - i, j)\)
• 左右反転 (3 B): \((i, j) \to (i, N - 1 - j)\)

よって、次の行列 \(M_{\mathrm{2A}}, M_{\mathrm{2B}}, M_{\mathrm{3A}}, M_{\mathrm{3B}}\) を考えると、操作 \(t\) によってマス \((i, j)\) が移る先 \((i', j')\) は、\(\begin{bmatrix} i' \\ j' \\ 1 \end{bmatrix} =~M_t \begin{bmatrix} i \\ j \\ 1 \end{bmatrix}\) として得られます。（関連：アフィン変換）

\[M_{\mathrm{2A}} =~\begin{bmatrix} & 1 & \\ -1 & & N-1 \\ & & 1 \end{bmatrix}, M_{\mathrm{2B}} =~\begin{bmatrix} & -1 & N-1 \\ 1 & & \\ & & 1 \end{bmatrix},\]

\[M_{\mathrm{3A}} =~\begin{bmatrix} -1 & & N-1 \\ & 1 & \\ & & 1 \end{bmatrix}, M_{\mathrm{3B}} =~\begin{bmatrix} 1 & & \\ & -1 & N-1 \\ & & 1 \end{bmatrix}\]

操作 \(t_1, t_2, \ldots, t_k\) を順に行ったときにマス \((i, j)\) が移る先 \((i', j')\) は

\[\begin{bmatrix} i' \\ j' \\ 1 \end{bmatrix} = M_{t_k} M_{t_{k-1}} \cdots M_{t_2} M_{t_1} \begin{bmatrix} i \\ j \\ 1 \end{bmatrix}\]

となるので、行列 \(M := M_{t_k} M_{t_{k-1}} \cdots M_{t_2} M_{t_1}\) を管理すればよいです。

クエリ \(2, 3\) については、\(M\) に左から \(M_t\) をかければよいです。

クエリ \(1\) については、移る先が \((i', j')\) になるマス \((i, j)\) を求め、 そのマスの色を更新する必要があります。これは、\(M\) の逆行列を用いて \(\begin{bmatrix} i \\ j \\ 1 \end{bmatrix} =~M^{-1} \begin{bmatrix} i' \\ j' \\ 1 \end{bmatrix}\) と求められます。逆行列を求めるライブラリを持っている場合はそれを活用してもよいですが、\(M_{\mathrm{2A}}^{-1} = M_{\mathrm{2B}}, M_{\mathrm{3A}}^{-1} = M_{\mathrm{3A}}, M_{\mathrm{3B}}^{-1} = M_{\mathrm{3B}}\) を利用して、\(M\) と同時に \(M^{-1}\) も管理すると、行列積のみで実装できます。