GYM 101147K Touristic Trip

首先可以看出这是一个条件概率 \(P(A/B) = \frac{P(AB)}{P(B)}\)，其中 \(A\) 事件为“满足在 \(Z\) 城市时寄出第 \(Q\) 张明信片”，\(B\) 事件为“满足得到的明信片序列与给出的明信片序列相同”
那只需要求出 \(P(AB)\) 和 \(P(B)\) 就能得到最终答案了

首先考虑 \(B\) 事件
发现这些要求都只与现在该寄出的明信片数和现在所在的城市有关，明信片序列是固定的，所以设 \(dp_{i, j}\) 为现在该寄出第 \(i\) 张明信片且现在在 \(j\) 城市满足 \(B\) 事件的概率
发现这个状态只可能由寄出上一张明信片时的任一城市的状态走来，即 \(dp_{i - 1, h}\) 推来，同时要乘上对应走过来的概率 \(P_{h, j}\)，但是还没有满足 \(B\) 事件，因为此时不能确保选到的明信片，所以再乘上 \(C_{j, a_i}\)，式子如下：
\(dp_{i, j} = C_{j, a_i}\sum\limits_{h = 0}^{n - 1} dp_{i - 1, h}\times dp_{h, j}\)

考虑 \(AB\) 事件该怎么做，发现其就是在 \(B\) 事件上多了个 \(A\) 事件的限制，直接沿用 \(B\) 事件的 \(\text{DP}\)
发现 \(A\) 事件的限制“该寄出第 \(Q\) 张明信片时只能通过 \(Z\) 城市”可以转化成“该寄出第 \(Q\) 张明信片时不能通过除 \(Z\) 的点”，那就挺好办了：
\(dp_{q, j} = 0\quad (j\not= Z)\)
其他的没有约束正常跑就行了

时间复杂度 \(O(kn^2)\)

无注释版本

#include<bits/stdc++.h>
using namespace std;
const int N = 20 + 2, M = 10 + 2, K = 15 + 2;
int n, m; int k, q, z;
double P[N][N], C[N][M]; int a[N];
double dpAB[K][N], dpB[K][N];
void solve() {
    scanf("%d%d%d%d%d", &n, &m, &k, &q, &z);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%lf", &P[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%lf", &C[i][j]);
        }
    }
    for (int i = 0; i < k; i++) {
        scanf("%d", &a[i]);
    }
    memset(dpAB, 0, sizeof(dpAB)), memset(dpB, 0, sizeof(dpB));
    dpAB[0][0] = (q == 0 && z != 0 ? 0 : C[0][a[0]]), dpB[0][0] = C[0][a[0]];
    // 注意判断当初始在 0 时就不能走的情况
    for (int i = 1; i < k; i++) {
        for (int j = 0; j < n; j++) {
            for (int h = 0; h < n; h++) {
                dpB[i][j] += dpB[i - 1][h] * P[h][j], dpAB[i][j] += dpAB[i - 1][h] * P[h][j];
            }
            dpB[i][j] *= C[j][a[i]], dpAB[i][j] *= C[j][a[i]];
            if (i == q && j != z) {
                dpAB[i][j] = 0;
                // 此时不能经过这个点
            }
        }
    }
    double ansAB = 0.0, ansB = 0.0;
    for (int i = 0; i < n; i++) {
        ansAB += dpAB[k - 1][i], ansB += dpB[k - 1][i];
    }
    printf("%.3lf\n", ansAB / ansB);
    // 条件概率
    return ;
}
int main() {
    freopen("trip.in", "r", stdin);
    int testcase;
    scanf("%d", &testcase);
    for (; testcase; testcase--) {
        solve();
    }
    return 0;
}