Black and white

$dp[i][j]$ を$2$ 行 $i$ 列のグリッドを白色と黒色のグリッドで塗りつぶしたとき、黒色のマスが隣接しない塗り方の数の内、一番右の列の状態がjのものの数とする. ただし、

• $j=0$ のとき上下のマスが白色
• $j=1$のとき、上のマスが黒色、下のマスが白色
• $j=2$のとき、上のマスが白色、下のマスが黒色 の状態とする。 このとき、

$dp[1][0]=dp[1][1]=dp[1][2]=1$

$dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]$

$dp[i][1]=dp[i-1][0]+dp[i-1][2]$

$dp[i][2]=dp[i-1][0]+dp[i-1][1]$

が成り立つ。 これを行列累乗などを用いて高速化することで、計算量は $O(logn)$ となる。