皆様どうもこんにちは！ばるとーくです！
今回は問題「Probability trip」の解説をしていきます！
問題
問題文
ばるとーく王国には、$1$ から $N$ までの番号が振られた $N$ 個の街がある。
王国全体では $M$ 本の道があり、$i$ 番目の道は街 $u_i$ と街 $v_i$ を双方向に結ぶ。
各街は必ず $1$ つ以上の他の街と双方向に行き来可能な道で結ばれており、全ての街は道を使って互いに行き来できることが保証される。
また、各街の間には道は多くとも $1$ 本しかなく、ひとつの街だけで完結する道は存在しない。冒険好きな少年ばる君は、$1$ 日目に街 $1$ にいる。
$2$ 日目以降の各日、ばる君は今いる街につながっている道の中から $1$ 本を等確率で選んで通り、その日に訪れる街へ移動する。
各日の移動は独立である。ある日、王国の占い師がばる君にこう告げた。
「あなたは、$S$ 日目には必ず街 $A$ を訪れるでしょう。」
この予言が真であるとき、ばる君が $T$ 日目（$1 \leq T < S$）に街 $B$ を訪れた条件付き確率を $\textrm{mod }998244353$ で求めよ。
なお、本問題の制約下で、条件付き確率が一意に定義されることが保証される。条件付き確率の $\textrm{mod }998244353$ とは
求める条件付き確率は必ず有理数になることが証明できます。
また、この問題の制約下では、その値を既約分数 $\frac{p}{q}$ で表したとき、$q \not\equiv 0\pmod{998244353}$ となることも証明できます。
よって、$R \times Q \equiv P \pmod{998244353}, 0 \le R < 998244353$ を満たす整数 $R$ が一意に定まります。
この $R$ を答えてください。制約
- $2 \leq N \leq 50$
- $N-1 \leq M \leq \dfrac{N(N-1)}{2}$
- $1 \leq u_i,\ v_i \leq N$、$u_i \neq v_i$（自己ループをもたない）
- $i \neq j$ のとき ${u_i,\ v_i} \neq {u_j,\ v_j}$（多重辺をもたない）
- 各街は必ず $1$ つ以上の他の街と双方向に行き来可能な道で結ばれている
- 全ての街は道を使って互いに行き来できる（各街は連結している）
- $1 \leq A ,\ B \leq N$
- $1 \leq T < S \leq 10^{18}$
- ばる君が $S$ 日目に街 $A$ にいる確率は $0$ でないことが保証される
- 求める条件付き確率は分母が $998244353$ と互いに素な既約分数で表せる
- 入力はすべて整数
解説
問題の概要はこんな感じです．
$N$ 頂点のグラフがある．各時刻に隣接頂点へ等確率で移動するランダムウォークを考える．
「day $S$ に都市 $A$ にいる」という条件のもとで、「day $T$ に都市 $B$ にいた」条件付き確率を求め，$\textrm{mod }998244353$ で出力せよ．
ただし，$T < S$ である．
確率漸化式から着想を得て，「未来から過去を参照する形」の条件付き確率を問う問題にしました．
ただし，この状態では「マルコフ性」がないため，過去の情報をすべて拾わなけばならず，処理が煩雑です．
※マルコフ性：「未来の状態は、現在の状態『だけ』で決まり、過去の経緯には一切影響されない」という性質1
そこで，まずは ベイズの定理 を用いてこの式を変形します．
ベイズの定理は以下の式で表されます．2
$P(X \mid Y) = \dfrac{P(Y \mid X)P(X)}{P(Y)}$
こうすることで，同時確率と周辺確率に分離するため，それぞれを順向きのランダムウォークとしてとらえることが可能になります．
また，マルコフ性が表れるようになるので，過去の情報がいらなくなるため，よりシンプルに考えることができます．
$\because$ 以下の2つの式を考えます．
$P(A \mid B) = \dfrac{P(A \land B)}{P(B)} \qquad \cdots (1)$
$P(B \mid A) = \dfrac{P(A \land B)}{P(A)} \qquad \cdots (2)$
この2つは皆さんおなじみの条件付き確率の式です．
$(2)$ を変形すると以下のようになります．
$P(A\land B) = P(B \mid A)P(A)$
さらに，遷移確率行列 $P$ を, 以下のように定めます．
$P_{i,j} = \begin{cases} 1/\deg(i) & ((i,j) \text{ が辺のとき}) \\ 0 & (\text{それ以外}) \end{cases}$
すると，$(P^k)_{i,j}$ は「頂点 $i$ からランダムウォークを $k$ 歩進めたとき，頂点 $j$ にいる確率」を表すことが知られています．
このとき，今回の量にベイズの定理を当てはめると，このような式になります．
ただし，「$S$ 日目に $A$」である事象を $X$, 「$T$ 日目に $B$」である事象を $Y$ とします．
$P(Y \mid X) = \frac{(P^{T-1})_{1,B} \cdot (P^{S-T})_{B,A}}{(P^{S-1})_{1,A}}$
これを，行列累乗を用いて実装しましょう．
繰り返し二乗法により $O(N^3 \log S)$ で計算することができます．
ちなみに，「$\textrm{mod }998244353$ ってなんだろう？」って方はこちらの記事を参考にしてみてください↓
※ばるとーく自身もこの問題を作る上ですっごくためになりました…！
想定解コードはyukicoderの解説ページを参考にして下さい．
