Random Walkers

解説

街 $u$ から直接繋がっている街の集合を $G(u)$ とします。ただし、$u$ から繋がっている道がない場合には、$G(u) = \{u\}$ とします。

この問題は動的計画法によって解くことができます。 $t ~ (\le T-1)$ 日目までに出会えた場合は以後二人は同じ街に留まるものとして、$dp[t][u][v]$ を

$$dp[t][u][v] = \text{「$t$ 日目の午後にみーとみが街 $u$, お茶の葉が街 $v$ にいる確率」}$$

とおきます（$0 \le t \le T,~1 \le u, v \le N$）。$t = 0$ については

$$dp[0][u][v] = \begin{cases} 1 &\mathrm{if}~u = P ~\mathrm{and}~ v = Q\\ 0 &\mathrm{otherwise} \end{cases}$$

とし、以後 $t = 0, 1, 2, \dots, T-1$ について

• $u \ne v$ なら, $$dp[t+1][x][y] \leftarrow dp[t+1][x][y] + \frac{1}{|G(u)|\cdot|G(v)|}dp[t][u][v] \qquad \text{for each $x \in G(u), y \in G(v)$}$$
• $u = v$ なら, $$dp[t+1][u][v] \leftarrow dp[t+1][u][v] + dp[t][u][v]$$

のように配るDPによって遷移させることで求めることができます。 出力する答えは $\sum_{u = 1}^{N} dp[T][u][u]$ です。 ただし $T$ が大きく愚直な遷移では間に合わないため、遷移を行列累乗によって高速化することで、$O(N^6\log T)$ で求まります。

なお二人の移動を別々に考え、たとえば $dp1[t][u] =$「$t-1$ 日目までに会ってなく、$t$ 日目にみーとみが街 $u$ にいる確率」、$dp2[t][u]$ をお茶の葉さんについての同様の確率として、「二人が $t$ 日目に街 $u$ で会う確率」$= dp1[t][u]\cdot dp2[t][u]$ のようにすることはできません（それらの事象が独立でないため）ので注意してください。