yukicoder No.3006 ベイカーの問題

hackに失敗して勉強になった

問題概要

$X_1,Y_1$が与えられる。$X_n,Y_n$を

\[\begin{align*} X_{n+1} &= X_1 X_n - 5Y_1 Y_n \\ Y_{n+1} &= Y_1 X_n + X_1 Y_n \end{align*}\]

で定めるとき$X_1+\dots+X_N,Y_1+\dots+Y_N$を$\mod 998244353$でそれぞれ求めよ。

解法

以下$p=998244353$とします。 \(A=\begin{pmatrix} X_1 & -5Y_1\\ Y_1 & X_1\\ \end{pmatrix}\) とすると \(\begin{pmatrix}X_N\\ Y_N\end{pmatrix} =A^{N-1} \begin{pmatrix}X_1\\ Y_1\end{pmatrix}\)なので \(\begin{pmatrix}X_1+\dots +X_N \\ Y_1+\dots+Y_N\end{pmatrix} =\left( 1+A+\dots+A^{N-1}\right) \begin{pmatrix}X_1\\ Y_1\end{pmatrix}\) になります。 従って$\left( 1+A+\dots+A^{N-1}\right) $を求めればよいです。これは等比数列の和と同様に $(I-A^N)/(I-A)$と$I-A$の逆行列が存在するとき書けます。 $\det(I-A) = (X_1-1)^2+5Y_1^2$です。$X_1\equiv 1,Y_1 \equiv 0$のとき$X_n\equiv 1,Y_n\equiv 0$なので$(N\mod p,0)$が答えです。問題はそれ以外で行列式が$0$と合同になる場合ですがそのような場合を考慮しないコードを提出したところ通りました■。そこでそのようなケースを作ってチャレンジしようと思い手元で計算してみましたが、一向にそのようなケースは作れませんでした。実はそのようなケースは存在しません。

$x^2+5y^2\equiv 0\mod p$ は$x\equiv y\equiv 0\mod p$に限る

一方が$0$と合同のとき条件はもう一方が$2$乗して$0$と合同になることですが、$p$は素数なので$x\equiv y\equiv 0$になります。両方$0$と合同でないとき、条件は$(x/y)^2\equiv -5$です。ここで次のことが知られています。

奇素数$p$と$a\not\equiv 0\mod p$に対して$m^2=a\mod p$となる$m$が存在する条件は$a^{\frac{p-1}{2}}\equiv 1\mod p$である

$(-5)^{\frac{p-1}{2}}\equiv -1 \mod p$なので$x\equiv y\equiv 0$以外で$x^2+5y^2\equiv 0$とならないことが分かりました。

別解

では行列式が$0$と合同になる非自明なケースがある場合はどうすればいいでしょうか？ただの数の場合の例が別の問題のユーザー解説にあり同じテクニックが使えます。すなわち \(\begin{pmatrix}A & I \\ O & I \end{pmatrix}^N = \begin{pmatrix}A^N & I+A+\dots+A^{N-1} \\ O & I \end{pmatrix}\) が成り立つので、$4\times 4$行列の行列累乗に帰着できます。