P2973 题解
Galois_Field_1048576
·
·
题解
设 \lambda = \dfrac pq。称现在处于 存活状态 当且仅当炸弹未爆炸。现在我们设 f_{n, i} 为走了 n 步，在节点 i，且存活的概率。容易发现 f_{n} \mapsto f_{n+1} 的转化是一个线性映射，而且其表示矩阵 \boldsymbol A 可以直接从这个有向图写出（a_{i,j} = \dfrac{1-\lambda}{\mathrm{deg}^{\rm out}_i}）。并且有 f_0 = \boldsymbol e_1（仅在第一分量为 1，后面的分量均为 0 的列向量）。
而一个炸弹在第 n 步爆炸的概率是 (1-\lambda)^{n-1} \lambda（注意需要带上在 n-1 步存活的概率），同理得炸弹在第 n 步，节点 i 爆炸的概率为 f_{n-1,i} \lambda = \lambda (\bm A^{n-1} \bm e_1)_i = \bm A^{n-1}_{1,i}。
现在当 n 对 1,2,3,\dots 求和：
\begin{aligned}
\mathrm{ans}(i) &= \sum_{n=1}^{+\infty} \lambda (\boldsymbol A^{n-1})_{1,i} \\
&= \lambda \left(\sum_{n=1}^{+\infty} \bm A^{n-1}\right)_{1,i} \\
&= \lambda \left(\sum_{n=0}^{+\infty} \bm A^n\right)_{1,i} \\
&= \lambda (\bm I - \bm A)^{-1}_{1,i}.
\end{aligned}
因此，对 \bm I - \bm A 求逆即可。