ABC204 F - Hanjo 2 (600)
最初の考察
最後の列の横にはみ出しているか$ 2^H通りを横が$ 2^0,2^1,2^2,\cdotsの場合について求める
$ 2^{i+1}の場合の答えは$ 2^iの結果から出す
これらを組み合わせて$ Wの場合の答えを出す
組み合わせ方がたくさんあるので駄目
最終的な考察
幅iの時の結果が幅i+1の時にどうなるかを次々計算していく
愚直にやると$ \mathcal{O}(W)で間に合わない
$ 2^Hの正方行列の行列累乗で考える
$ \mathcal{O}(\log W)になる
行列の$ i行$ j列目は$ iの立っているビット部分がはみ出している状態から$ jの立っているビットの状態がはみだしている状態になりうるパターンの数を表す
これは実際にありうるパターンで並べたときにどう変化するかを記録する
一列目のあり得るパターンについても実際に事前に試して調べておく
一列目のパターンに変化の仕方を表す行列を行列累乗で求めるだけ
累乗は$ H乗ではなく一列目を除いた$ H-1乗なので注意
累乗する行列を作る部分が$ \mathcal{O}(10^H H)、行列累乗部分が$ \mathcal{O}(8^H \log W)