ICPC – Regional 2012 – C: One-Dimensional Cellular Automaton を解いた記録

問題の概要

\(N\)個のセルがあり，各セルには\(0, 1, \dots, N-1\)の番号が付けられている．
各セルの値は常に正の整数\(M\)未満である．各セルの値は非負整数値で表される時刻\(t\)が進む（増える）ごとに変化する．
時刻\(t\)における\(i\)番目のセルの値を\(S(i, t)\)で表す．
時刻\(t+1\)における\(i\)番目のセルの値は，非負整数\(A, B, C\)を用いて次式で定義される．

\(S(i, t+1) = (A \times S(i-1, t) + B \times S(i, t) + C \times S(i+1, t)) \mod M\)

ただし，\(0 \leq i \leq N-1\)を満たさない場合は\(S(i, t)=0\)とする．

各セルの初期値\(S(0, 0), S(1, 0), \dots, S((N-1), 0)\)と正の整数\(T\)が与えられる．
\(S(0, T), S(1, T), \dots, S((N-1), T)\)を求めよ．

問題へのリンク

制約

• \(1 \leq N \leq 50\)
• \(1 \leq M \leq 1000\)
• \(0 \leq A, B, C \leq M-1\)
• \(0 \leq T \leq 10^{9}\)
• 入力はすべて整数

解法

セルの値の変化を行列で表現します．例えば\(N=4\)のときは次のようになります．
\[
\begin{pmatrix}
S(0, t) \\
S(1, t) \\
S(2, t) \\
S(3, t) \\
\end{pmatrix}
=
\begin{pmatrix}
B & C & 0 & 0 \\
A & B & C & 0 \\
0 & A & B & C \\
0 & 0 & A & B \\
\end{pmatrix}
\begin{pmatrix}
S(0, t-1) \\
S(1, t-1) \\
S(2, t-1) \\
S(3, t-1) \\
\end{pmatrix}
\]
よって，\(t=T\)のときのセルの値は行列の累乗を用いて次のように表せます．
\[
\begin{pmatrix}
S(0, T) \\
S(1, T) \\
S(2, T) \\
S(3, T) \\
\end{pmatrix}
=
\begin{pmatrix}
B & C & 0 & 0 \\
A & B & C & 0 \\
0 & A & B & C \\
0 & 0 & A & B \\
\end{pmatrix}^{T}
\begin{pmatrix}
S(0, 0) \\
S(1, 0) \\
S(2, 0) \\
S(3, 0) \\
\end{pmatrix}
\]

したがって，行列の累乗を高速に計算できればこの問題を解けます．行列の累乗は繰り返し2乗法の応用で高速に計算できます（競技プログラミングにおけるDPの考え方 ~繰り返し２乗法と行列累乗~ – サンリオピューロランドなどを参照）．

実装例

以下のコードでは，時刻\(t\)のときのセルの値から時刻\(t+1\)のときのセルの値を求める式が上記のものとは異なります．