アルゴリズムと数学057 - Domino Tiling 解法: 行列冪乗 これも遷移が線形になるので，行列冪で解ける． 状態を \(2^{K}\) で持っておき， 次数\(2^{K}\)の行列を考える． まず\(N\)が小さい場合で考えてみる． DP による全探索をすると， 左から \(i\) 列目…

アルゴリズムと数学056 - Recurrence Formula 2 解法: 行列冪乗 遷移が線形なので，行列冪により \(O(M^{3} log N)\) で求まる． ここで，\(M\)が行列の次数，\(N\) は行列冪の指数． 遷移が \[ \begin{pmatrix} a_{n} & a_{n+1} & a_{n+2} \end{pmatrix} = …

アルゴリズムと数学062 - Teleporter 解法0: 周期性を用いる \(i \rightarrow a[i]\) と遷移を繰り返すと，あるところでサイクルに入る． \(i_{0}\)からスタートするとして， \[ i_{0} \rightarrow \cdots a \rightarrow b \rightarrow \cdots \rightarrow c…