エクサウィザーズプログラミングコンテスト2021 (ABC 222) G - 222

• 問題
• 提出

与えられた数列を$(a_i)_{i = 0}^\infty \ (a_0=0, a_1 = 2, a_2 = 22, ...)$とする。$M = \begin{bmatrix} 10 & 2 \\ 0 & 1\end{bmatrix}, v= \begin{bmatrix} 0 \\ 1\end{bmatrix}$とするとき、$a_k$は$M^k v$の第一成分に等しい。従って、問題は$v = M^kv$であるような最小の正整数$k$を求めることと言い換えられる。

この問題はbaby-step giant-stepで解ける。$B= \lceil \sqrt K \rceil$とする。$a_0, a_1, a_2, ..., a_{B-1}$について$\mod K$での値をmapのキー、添字をmapの値として保持しておく。（キーが重複する場合、そこでサイクルに入るので、それまでに$0$が見つかっていなければ打ち切ってよい。） $k= iB-j$, $j \in \{0, 1, ..., B-1\}$とする時、$v = M^kv$が成り立つためには$M^j v = M^{iH}v$が成り立つ必要がある。したがって、$i=1, 2, ..., B$について$M^{iB}v$を計算して$a_{iB}$を求め。この値が先に作ったマップに入っていれば対応する添字$j$を取り出すと$k=iB-j$が答えの候補になる。ただし、$M$は正則とは限らないので、$M^j v = M^{iB}v$は必要条件でしかない。つまり、$a_{iB-j} \mod K$が必ず$0$になるわけではない。実際に$M^{iB-j}v$を計算して確認する必要がある。

ハッシュテーブルを使った場合の期待計算量は${O}(\sqrt K)$。