問題

建物のH階部屋1から1階部屋1に移動するパターンを求める。同じフロアでは部屋 $i, j$ は $g_{i,j} = 1$ なら隣接していて、同じ部屋は2回通れない。フロア間は同じ番号の部屋へ一方方向に降りるだけ。

考察

フロア内の移動

任意の部屋 $i$ からスタートし、同じ部屋を通らずに移動して、部屋 $j$ で階を降りるパターン $p_{i, j}$ を求める。

部屋 $s$ から通ってない残りの部屋の状態 $s$ を保持しながら移動する。現在の部屋 $n$ から部屋 $t$ に遷移できる条件は、 $s_i = 1, g_{n,t} = 1$ のときである。 $p_{s, t}$ は、全ての状態で部屋 $t$ に達するパターンの総和である。全ての $s \in [1, R$ ]についてこれを計算する。