解题思路（动态规划）

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

状态定义

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

转移方程

只允许从非 x 状态转到非 x 状态：

同时保持 dp[t][x] = 0。

初始条件与答案

• 初始：dp[0][s] = 1，其余为 0。
• 答案：$\sum_{j\neq x} dp[k][j]$（第 $k$ 步仍未到达 $x$ 的总概率）。

复杂度分析

每步转移需枚举所有 i→j（i,j≠x），复杂度 $O(n^2)$，总计 $O(k\,n^2)$。 在约束 $n\le 50,\; k\le 200$ 下，计算量 $\le 5\times 10^5$ 次乘加，轻松通过。

参考实现

Python

import sys

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    s = int(next(it)) - 1  # 改为0索引
    x = int(next(it)) - 1
    k = int(next(it))
    P = [[float(next(it)) for _ in range(n)] for _ in range(n)]

    # dp[t][i]: 走了t步、未到达x、在i的概率
    dp = [0.0] * n
    dp[s] = 1.0

    for _ in range(k):
        ndp = [0.0] * n
        # 仅在 i != x、j != x 之间转移
        for i in range(n):
            if i == x or dp[i] == 0.0:
                continue
            pi = P[i]
            for j in range(n):
                if j == x:
                    continue
                ndp[j] += dp[i] * pi[j]
        dp = ndp

    # 末状态不限：累加所有 j != x
    ans = sum(dp[j] for j in range(n) if j != x)
    # 若要求“回到 s ”：改为 ans = dp[s]

    print(f"{ans:.6f}")

if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    int s, x, k;
    cin >> s >> x >> k;
    --s; --x; // 改为0索引
    vector<vector<double>> P(n, vector<double>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> P[i][j];

    vector<double> dp(n, 0.0);
    dp[s] = 1.0;

    for (int step = 0; step < k; ++step) {
        vector<double> ndp(n, 0.0);
        for (int i = 0; i < n; ++i) {
            if (i == x || dp[i] == 0.0) continue; // 不能从x出发
            for (int j = 0; j < n; ++j) {
                if (j == x) continue;             // 不能到达x
                ndp[j] += dp[i] * P[i][j];
            }
        }
        dp.swap(ndp);
    }

    double ans = 0.0;
    for (int j = 0; j < n; ++j)
        if (j != x) ans += dp[j];
    // 若要求“回到 s ”：改为 ans = dp[s]

    cout.setf(std::ios::fixed); cout << setprecision(6) << ans << "\n";
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String t = sc.next();
        if (t == null) return;
        int n = Integer.parseInt(t);
        int s = sc.nextInt() - 1;  // 改为0索引
        int x = sc.nextInt() - 1;
        int k = sc.nextInt();

        double[][] P = new double[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                P[i][j] = sc.nextDouble();

        double[] dp = new double[n];
        dp[s] = 1.0;

        for (int step = 0; step < k; step++) {
            double[] ndp = new double[n];
            for (int i = 0; i < n; i++) {
                if (i == x || dp[i] == 0.0) continue; // 不从x转移
                for (int j = 0; j < n; j++) {
                    if (j == x) continue;             // 不到x
                    ndp[j] += dp[i] * P[i][j];
                }
            }
            dp = ndp;
        }

        double ans = 0.0;
        for (int j = 0; j < n; j++)
            if (j != x) ans += dp[j];
        // 若要求“回到 s ”：改为 ans = dp[s]

        System.out.printf("%.6f%n", ans);
    }
}

题目内容

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

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

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

小明刚刚处理完事件 $s$，他将连续处理 $k$ 个事件。在整个处理过程中，不能出现事件 $x$（即处理序列中不允许包含 $x$ 事件）。

请你计算：发生这个复杂事件的概率是多少？

输入格式

• 第一行：一个整数 $n$ — 事件的个数（$1 \le n \le 50$）

• 第二行：三个整数 $s, x, k$

  • $s$ — 起始事件编号（$1 \le s \le n$）
  • $x$ — 不允许处理的事件（$1 \le x \le n ,x \neq s$）
  • $k$ — 处理的事件个数

  注意：这里的“处理的事件个数 $k$”指从初始状态开始，依次经历 $k$ 次状态变化后结束的路径长度。

• 接下来 $n$ 行，每行 $n$ 个实数，第 $i$ 行第 $j$ 列为 $P(i,j)$，即从事件 $i$ 转移到事件 $j$ 的概率。 每行的概率和为 $1$，每个概率满足 $0 \le P(i,j) \le 1$。

数据保证

$40\%$的数据满足:$k \leq 7$

$100\%$的数据满足:$k \leq 200$

输出格式

• 输出一个实数，表示所求概率。
• 答案保留6位小数

样例输入

3
1 2 2
0.5 0.5 0
0.2 0.3 0.5
0.4 0.5 0.1

样例输出

0.250000

说明

样例中：

• 事件总数为 $n = 3$
• 起点 $s = 1$
• 不允许出现的事件 $x = 2$
• 处理 $2$ 个事件（即转移 $2$ 步）