概要
解法
基本的なところは解説スライドがあるので省略します。
この問題は、
- 状態ごとの数え上げを表すベクトル $v$
- 遷移を表す疎行列 $A$
を用いて、$A^T v$ の成分の和として書くことができます。$A$ の大きさを $N = O(H^{1.5})$ とします。また、$A$ の非零成分は $O(N)$ 個しかありません。よって、この問題は、以下の方法で $O(N^2 + N\log N\log T)$ 時間で解くことができます。
- $T = 1, 2, \ldots, 2N$ に対する答を計算する。疎行列をベクトルに掛けていけばよく、全体として $O(N^2)$ 時間である。
- Berlekamp-Massey 法を用いて、線形漸化式を復元する。$O(N^2)$ 時間である。
- Fiduccia’s algorithm や Boston-Mori algorithm などを用いて、線形漸化式の第 $T$ 項を求める。$O(N\log N\log T)$ 時間である。
