テスト投稿 ABC113D Number of Amidakuji

D - Number of Amidakuji

問題

H : 横線を引くことのできる段数
W : 縦線の本数
のあみだくじを考えたとき, 1本目からK本目へいたるあみだくじの総数を1e9+7で割った余りを求めよ.

制約

• $ 1 \le H \le 100 $
• $ 1 \le W \le 8 $
• $ 1 \le K \le W $

解法

あみだくじのパターン数はO(2 ^ HW)全探索 DP