解题思路（动态规划）

把所有到达 $x$ 的路径视为“失败”（概率计为 0），只在其余状态之间做概率累积。

状态定义

令 dp[t][i] 表示：从起点 s 出发，走了 t 步，且整个过程未到达 x，此时停在状态 i 的概率（其中 i ≠ x）。

转移方程

题目内容

随机游走模型（Random Walk Model）是一种随机过程（stochastic process），用来描述一个变量随时间的变化路径，其中每一步的变化是由随机误差或概率转移决定的，并且这些变化相互独立、同分布。它常用于刻画股票价格、汇率等金融时间序列的不可预测性。

在本题中，我们有 $n$ 个不同的事件（状态），编号为 $1, 2, \dots, n$ 。

在任意两个事件 $i, j$ 之间，有一个转移概率 $P(i, j)$，表示当当前事件是 $i$ 时，下一事件是 $j$ 的概率。所有转移概率构成一个 概率转移矩阵 $P$，满足每行之和等于 $1$，且 $P(i,j) \ge 0$。