No.020 D

道 $i$ を町 $i$ と町 $i+1$ をつなぐ道とする.

道 $i$ を通るということは, $i$ 以下の町から $i+1$ 以上の町を移動するということである.

そこで, $i$ 以下の町を $1$, $i+1$ 以下の町を $0$ として訪れる順序を並べた2進数の数値 $j$ を考える. 例えば道 $3$ について, $2, 4, 3, 7, 5, 1$ と町を訪れたとすると, $j = 101001_{(2)}$ となる. $j$ の $i$ ビット目と $i+1$ ビット目が違うならば道 $i$ を通るということになる. この数値から出される道 $i$ の通過回数を $f(j)$ とおく.

ここで, 道 $i$ まで見たときに訪れる順序を並べた2進数が $j$ になり, そこまでの移動距離の合計を $M$ で割った余りが $m$ となる組み合わせを $A(i, j, m)$ として, これを更新していく.

$i$ 番目の道において $j$ の $k$ ビット目を $1$ にするということは, 町 $i$ を $k$ 番目に訪問するということであり, $k$ ビット目を $1$ にした値を $j^{\prime}$ とする. そうすると,

$$A(i, j^{\prime}, m+D_i f(j^{\prime})) += A(i-1, j, m)$$

となる. また, $i$ 番目の町を訪問しないという選択肢もあるので,

$$A(i, j, m+D_i f(j)) += A(i-1, j, m)$$

となる.