問題
縦棒が $w$ 本、$h$ 段で $0$ 番が $k - 1$ 番に到達するようなあみだくじの個数を求めよ。（$h\leq100$, $w\leq8$）
解説
$i + 1$ 段で $j$ に到達するには $i$ 段で $j - 1$、$j$、$j + 1$ のいずれかにいればよい。 それぞれの場合について関係ない部分は自由に線を引ける。
$j - 1$ から $j$ に行く場合 左 $j - 2$ 個の枠と右 $w - j - 2$ 個の枠に自由に線を引ける。
$j$ から $j$ に行く場合 左 $j - 1$ 個の枠と右 $w - j - 2$ 個の枠に自由に線を引ける。
$j + 1$ から $j$ に行く場合 左 $j - 1$ 個の枠と右 $w - j - 3$ 個の枠に自由に線を引ける。
あみだくじでは隣り合う枠両方に線を引いてはいけないことに注意。 $k$ 個の枠に隣り合わないように線を引く組合せの個数を$F[k]$とすると、$0$ 個の枠には線を引けないので $F[0] = 1$、$1$ 個の枠には線を引くか引かないかで $F[1] = 2$、$k\geq 2$ のとき $k$ 個目に線を引くなら $F[k - 2]$ 通り、$k$ 個目に引かないなら $F[k - 1]$ 通りだから $$F[k] = F[k - 1] + F[k - 2]$$ が成り立つ。
$DP[i][j]$ を上から $i$ 段で $j$ に到達するあみだくじの個数とすると、遷移式は $$ \begin{aligned} DP[i][j] &= DP[i][j - 1]\times F[j -2]\times F[w -2- j] \\ &+ DP[i][j ]\times F[j -1]\times F[w -2- j] \\ &+ DP[i][j + 1]\times F[j -1]\times F[w -3- j] \\ \end{aligned} $$ となる。
実装
インデックスが $0$ 未満になったり $w -1$ を超えたりしたときにバグらないために $DP[i]$ と $F$ の末尾に番兵を置いている。
h, w, k = map(int, input().split()) p = 10**9+7 DP = [[0 for j in range(w+1)] for i in range(h+1)] DP[0][0] = 1 F = [1, 2, 3, 5, 8, 13, 21][:w]+[1] for i in range(h): for j in range(w): a = DP[i][j-1]*F[j-2]*F[w-2-j] b = DP[i][j]*F[j-1]*F[w-2-j] c = DP[i][j+1]*F[j-1]*F[w-3-j] DP[i+1][j] = (a+b+c) % p print(DP[h][k-1])
