随机游走基础板题解

· · 个人记录

U550679 随机游走基础板

首先思考下走到点 n 便立即停止这个机制存在的意义是什么，不难发现这其实相当于保证了图上至少有一个点出度为 0（点 n 的出边显然可以忽略，什么用都没有）。

于是我们得到了可能的终点集合 S，它由所有出度为 0 的点与点 n 组成。

思考完这些就可以开始求解了，发现有多个询问，暂先不予理会，对 x 单独进行求解：

令 dp_i 表示当前在 i 点，最终路径倒数第二个点为 x 的概率。deg_i 为点 i 的出度。据定义，答案为 dp_1。

转移很简单：

dp_i=\sum\limits_{j=1}^n \frac{dp_j\times a_{i,j}}{deg_i}

特别的，在进行 i=x 的转移时，对于 j\in S，有 dp_j=1；而在进行 i\ne x 的转移时，对于 j\in S，则有 dp_j=0。

发现转移成环，考虑解方程，没性质，只能暴力高消。单次询问复杂度 O(n^3)，总复杂度 O(n^4)。

注意到对于所有询问，高斯消元时的原矩阵是一模一样的，每次变化的只有矩阵旁边挂着的列向量（因为只修改了部分 dp_j 的值，而修改前后都是常数）。所以只要记录下该矩阵的消元过程，每次询问再对着列向量单独做一遍就行了。预处理复杂度 O(n^3)，单次询问复杂度 O(n^2)，总复杂度 O(n^3)。