TDPC M - 家

• 問題
• AC

部屋$i,j \in\{1,...,R\}$と部屋の集合$S\subseteq\{1,...,R\}$が与えられたとき、$i$から$j$への経路で$S$に含まれるすべての部屋をちょうど1回ずつ通るものの数を$f(i,j,S)$とする。部屋$j$に隣接する部屋の集合を$N(j)$とすると、$f$の漸化式は

$$f(i,j,S)= \begin{cases} 1 & (S=\{i\}=\{j\}) \\ \sum_{k \in S∩N(j)}f(i,k,S \setminus \{j\}) & (i,j \in S)\\ 0 & (それ以外) \end{cases}$$

と書ける。さらに、$a_{ij}$​を部屋$i$から$j$への経路の総数として行列$A=(a_{ij}) \in \mathbb Z^{R\times R}$を与えると、$a_{ij}$​は$f$を使って

$$a_{ij}​=\sum_{S\subseteq \{1,...,R\}}​f(i,j,S)$$

と書ける。DPすれば$A$は$O(R^32^R)$で求まる。

さて、ある階の部屋$i$からひとつ下の階の部屋$j$への経路の総数は$\sum_{k=1}^Ra_{ik}a_{kj}$で求まり、これは$A^2$の$i$行$j$列に等しい。帰納的に、$H$階の部屋1から1階の部屋1への経路の総数は$A^H$の第1行第1列に等しいことがわかる。全体の計算量は$O(R^32^R+R^3\log ⁡H)$。