024号文書

主にプログラミング

ABC113 D - Number of Amidakuji

ABC

問題

ABC113 D - Number of Amidakujiです。

解法

方針

まず、求める解を漸化式で表します。 漸化式から解を求めるのはプログラムで地道に計算します。

ざっくりと漸化式を定義する

縦棒 jの上から i cm目のちょっと下に（上から icm目の横棒を移動した後ということ）たどり着くことができる 高さ i cm目までの正しいあみだくじの本数を a_{i, j} とします。 求める解は a_{H, K} です。

初期条件

縦棒1の上端からあみだくじは開始するので、以下が成り立ちます。

  • a_{0, 1} = 1
  • a_{0, j} = 0 (j \geq 2)

また、便宜上、 j \leq 0 または j \geq W + 1 を満たす jについて、 a_{i, jj}=0 と定義しておきます。

漸化式

縦棒 jの上から i cm目のちょっと下に（上から icm目の横棒を移動した後ということ）たどり着くパターンは以下の3通りです。

  • 縦棒 j - 1の上から i - 1 cm目のちょっと下（上から i - 1cm目の横棒を移動した後ということ）を通過し、 上から icm目の縦棒 j-1, jを繋ぐ横線をたどってくるパターン
  • 縦棒 jの上から i - 1 cm目のちょっと下（上から i - 1cm目の横棒を移動した後ということ）を通過し、そのまま真下にたどってくるパターン
  • 縦棒 j + 1の上から i - 1 cm目のちょっと下（上から i - 1cm目の横棒を移動した後ということ）を通過し、 上から icm目の縦棒 j, j+1を繋ぐ横線をたどってくるパターン

また、上記の各パターンについて、上から i cm目の横棒には自由度があることに注意します。 例えば、一つ目のパターンでは、縦棒 j-1, jを繋ぐ横線させあれば、 縦棒 j+1, j+2を繋ぐ横線があろうがなかろうが構いません （正しいあみだくじとするため、縦棒 j-2, j-1を繋ぐ横線、および、縦棒 j, j+1を繋ぐ横線は引けないことに注意してください）。 上記のパターン分けと自由度から以下の形の漸化式を得ます。

a_{i, j}= c_{1, j-2} c_{j+1, W} a_{i-1, j-1} + c_{1, j-1} c_{j+1, W} a_{i-1, j} + c_{1, j-1} c_{j+2, W} a_{i-1, j+1}

cは自由度を表す係数です。 縦棒 jから縦棒 j'までの間に（正しいあみだくじであるように）横線を引くパターン数を c_{j, j'}で表しています。 ただし、 j \geq j' ならば c_{j, j'} = 1 とします。

あとは、 cを解析すれば、 a_{H, K}を計算できます。

cを解析する

j \geq j' ならば c_{j, j'} = 1 としているので、いったん、 j < j' として議論します。

まず、縦棒 j, j'の間には横線を引けるスペースが j' - j個あります。 スペースの数だけに依存するので、 c_{j, j'} = F_{j'-j} で表せます（スペースの数が k個のときの横線を引くパターン数を F_{k} で表してます）。

まず、連続したスペースに横線を引けない制約から、 F_{1}=2, F_{2}=3 は直ちにわかります。 さらに、最も左のスペースに横線を引く場合、その右のスペースに横線は引けないので、 F_{k}=F_{k-1} + F_{k-2} という漸化式を得ます。 すなわち、（初期条件は少し異なりますが） F_{k} はフィボナッチ数列です。

さらに、 j \geq j' ならば c_{j, j'} = 1 なので、 F_{k} = 1 (k \leq 0) と定義しておくと計算の都合がよいです。

以上より、 c_{j, j'} は上記フィボナッチlikeな値 F_{j'-j} で求められることがわかりました。

求める解のまとめ

以下の漸化式について、 a_{H, K} が求める解です。

  • a_{0, 1} = 1
  • a_{0, j} = 0 (j \geq 2)
  • a_{i, j} = 0 (j \leq 0 \lor j \geq W + 1)
  • a_{i, j}= F_{j-3} F_{W-j-1} a_{i-1, j-1} + F_{j-2} F_{W-j-1} a_{i-1, j} + F_{j-2} F_{W - j - 2} a_{i-1, j+1}

ただし、

  • F_{k} = 1 (k \leq 0)
  • F_{k} = F_{k-1, k-2} (k \geq 1)

です。 また、解を出力する際は1000000007の剰余をとることを忘れないように注意してください。

ACしたコード

from functools import lru_cache

H, W, K = map(int, input().split())
def f(k):
  return 1 if k <= 0 else f(k-1) + f(k-2)
@lru_cache(maxsize=H*W)
def a(i, j):
  if j < 1 or j > W or (i == 0 and j != 1):
    return 0
  if i == 0 and j == 1:
    return 1
  return (f(j-3) * f(W-j-1) * a(i-1, j-1) + f(j-2) * f(W - j - 1) * a(i - 1, j) + f(j - 2) * f(W - j - 2) * a(i - 1, j + 1)) % 1000000007
ans = a(H, K)
print(ans)