問題概要

問題文はこちらを参照してください。

巡回セールスマン問題(TSP)のようにbitDPで解く必要があります。

解法

同じ構造の階がたくさんあって、降りる方向にしか進めないということなので、ある階において部屋$j$に上から降りてきて、部屋$i$で次の階に降りるまでの経路の数がわかっていて$a_{ij}$とします。また、その階に降りてくる時までの経路の数はわかっていて、それぞれの部屋$j$に降りてきた時の経路の数を$x_j$とします。すると、その階の部屋$i$で次に降りる経路の数は、$\displaystyle\sum_{j=0}^{R-1}a_{ij}\cdot x_j$となります。部屋$i$で次に降りる経路の数を$y_i$とすると、これは行列の積で表すことができます。(部屋番号は0-indexedに変更)

$$\left(\begin{array}{c}y_0 \\ y_1 \\ \vdots \\ y_{R-1}\end{array}\right) = \left( \begin{array}{cccc} a_{00} & a_{01} & \ldots & a_{0R-1} \\ a_{10} & a_{11} & \ldots & a_{1R-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{R-1\ 0} & a_{R-1\ 1} & \ldots & a_{R-1\ R-1} \end{array} \right) \left(\begin{array}{c}x_0\\x_1\\\vdots\\x_{R-1}\end{array}\right)$$

1階分の計算はこのようになるので、この演算を繰り返し行うことで、$H$階分降りたときの経路の数を求めることができます。

$$\left(\begin{array}{c}y_{H0} \\ y_{H1} \\ \vdots \\ y_{H\ R-1}\end{array}\right) = \left( \begin{array}{cccc} a_{00} & a_{01} & \ldots & a_{0R-1} \\ a_{10} & a_{11} & \ldots & a_{1R-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{R-1\ 0} & a_{R-1\ 1} & \ldots & a_{R-1\ R-1} \end{array} \right)^H \left(\begin{array}{c}1\\0\\\vdots\\0\end{array}\right)$$

最初は部屋$0$からスタートするので、$x_0$のみ$1$でそれ以外は$0$、$H$階の部屋$0$まで行く経路なので、求める答えは$y_{H0}$になります。

普通に行列の掛け算を1回やるのに$O(R^3)$かかりますが、行列の累乗を繰り返し二乗法で行うことで、$O(R^3\log H)$で求めることができ、これなら間に合いそうです。

次に、この行列$A$を求める方法ですが、巡回セールスマン問題(TSP)のようにbitDPで求めることができます。

一般的なTSPはある場所からスタートして、重複なくすべての都市を回って、移動コストが最小となる経路を求める問題ですが、今回は、ある部屋からスタートして、重複なくある部屋に行く経路の組み合わせの数を求めるという問題になります。

同じ部屋は通らないということなので、部分問題としてすでに通った部屋の集合と、今いる部屋と、そこに来るまでの経路の個数がわかっているとします。すると、今いる部屋から行くことができて、まだ通っていない部屋に行くまでの経路の個数に、今いる部屋に来るまでの経路の個数を足していく(配るＤＰ)と次の部屋の経路数が求められます。

漸化式の定義： $$dp[S_i\cup\{u\}][j]=dp[S_i\cup\{u\}][j]+dp[S_i][j]$$

$dp[i][j]$：今部屋$j$にいて、集合$S_i$で表される部屋をすでに通ってきた時の経路の数

$S_i$：すでに通ってきた部屋の番号の集合。

$i$：集合$S_i$の要素(0～15の値)を$i$のビットの位置とみなして、要素に含まれる部屋番号のビットを1とした場合の整数。

$j$：現在いる部屋の番号。

$u$：現在いる部屋$j$から行くことができで、すでに通ってきた部屋に含まれない部屋の番号($g_{j,u}=1\land u\not\in S_iを満たすu$)

$(1\le i \lt 2^R,\ 0\le j\lt R,\ 0\le u\lt R)$

初期値：$dp[\{s\}][s]=1$

求める解：$a_{es}=\displaystyle\sum_{i=1}^{2^R-1}dp[i][e](0\le e\lt R)$

$s$：その階での最初の部屋

$e$：その階での最後の部屋

$u$のループは、$0～R-1$を回して条件が合う時のみ計算します。

$s$を決めてこの漸化式を解くと、$s$から全ての$e$への経路の数が求まります。$s$を全部屋で回すことで、それぞれの部屋から他の部屋への経路の数、行列$A$が求まります。

$i,j,u,s$のループで、$O(2^R\cdot R^3)$になります。

考察

bitDPは、集合$S_i$の要素を整数$i$のビットに割り当てたときに、($S_i$の整数表現)$\lt$($S_i\cup\{u\}$の整数表現)という性質($S_i\subset S_i\cup\{u\}$なので)を使って、ループを$1$から$2^R-1$まで回せばよいというのを理解しておく必要があります。

また、集合の足し算(和集合)や集合にある要素が含まれるかどうかを、ビット演算で実装することも必要です。

集合の足し算(和集合)$S_i\cup\{u\}$：$i\ |\ (1 << u)$

$u\not\in S_i$の真偽：$(i\ \&\ (1 << u)) == 0\ (S_i$に含まれなければ真)