游戏 - 题解

标签与难度

标签: 动态规划, 概率DP, 前后缀DP, 模运算, 博弈论难度: 1900

喵？是新游戏！题目大意喵~

各位Master，欢迎来到石头剪刀布的战场，喵~ 这次有 $n$ 位勇士，编号从 $1$ 到 $n$ ，要进行一场盛大的淘汰赛！

比赛规则是这样的说：

固定手势：每位勇士在游戏开始前，会从自己的可选动作集合（比如某人只能出石头和布）中，等概率地选择一个手势，并且在整个游戏过程中 不再改变！
车轮战：比赛一轮接一轮。
- 第1轮：勇士1 对战勇士2。
- 第 $i$ 轮（ $i \ge 2$ ）：上一轮的胜利者，将迎战新的挑战者——勇士 $i+1$ 。
- 就这样，直到决出最后的总冠军！这就像是守擂台一样，胜利者要一直战斗下去，喵~
胜负规则：
- 石头胜剪刀，布胜石头，剪刀胜布。
- 如果两人出了一样的手势，那么 编号小 的那位获胜。

我们的任务是，对于每一位勇士，计算出他最终赢得整场比赛的概率是多少。因为是概率题，结果要对 $998244353$ 取模哦！

解题思路分析，跟着我的思路来喵！

这道题看起来有点复杂，因为每个人的选择都充满了不确定性，而一连串的比赛又把所有人的命运联系在了一起，呐。不过别担心，让我来庖丁解牛，一步步解开谜题！

核心思想：拆解胜利之路

我们来想一下，编号为 $i$ 的勇士要怎样才能成为最终的冠军呢？他的胜利之路可以分为两段，喵~

挑战成功：首先，他得在第 $i-1$ 轮比赛中登场，并击败从前面 $1, 2, \dots, i-1$ 号勇士中杀出来的胜利者。只有赢了这一场，他才有资格继续走下去！
守擂成功：在击败了前面的所有对手后，勇士 $i$ 就成了新的擂主。接下来，他必须像一位真正的国王一样，接受来自 $i+1, i+2, \dots, n$ 号勇士的轮番挑战，并全部取得胜利！

你看，一个人的胜利概率，取决于他 前面的战局 和 后面的战局。这种“一个点依赖其前缀和后缀信息”的结构，强烈地暗示了我们可以使用 前后缀DP 的方法来解决！

我们可以分别计算出两部分的概率，然后把它们乘起来，就能得到勇士 $i$ 以某种特定方式获胜的概率啦。

手势的奇妙映射，喵~

为了方便计算，我们给石头、剪刀、布编个号。但是，如果按照常规的0=石头, 1=布, 2=剪刀，关系式会是 (j+1)%3 克 j 吗？

布(1) 克石头(0) -> (0+1)%3=1，对。
剪刀(2) 克布(1) -> (1+1)%3=2，对。
石头(0) 克剪刀(2) -> (2+1)%3=0，对。

哇，这个映射太完美了！j 被 (j+1)%3 克制。但是，j 克制谁呢？j 克制的是 (j-1+3)%3，也就是 (j+2)%3。

不过，我在偷看其他大佬的代码时发现了一个更简洁的表示方法！如果我们这样定义：

0 = 石头 (Rock)
1 = 剪刀 (Scissors)
2 = 布 (Paper)

会发生什么奇妙的事情呢？

0 (石头) 克 1 (剪刀) => 0 克 (0+1)%3
1 (剪刀) 克 2 (布) => 1 克 (1+1)%3
2 (布) 克 0 (石头) => 2 克 (2+1)%3

天哪！在这种映射下，手势 j 恰好克制手势 (j+1)%3！这让我们的状态转移方程变得超级整洁，喵~ 接下来我们就采用这个神奇的映射。

前缀DP：`dp_prefix[i][j]`

让我们定义 dp_prefix[i][j] 为：只考虑前 i 个勇士的情况下，最终胜利者出手势 j 的概率是多少。

基础 (Base Case): 当只有勇士1时，他就是胜利者。所以 dp_prefix[1][j] 就是勇士1出手势 j 的概率。
转移 (Transition): 如何从 dp_prefix[i-1] 推导出 dp_prefix[i] 呢？在第 $i-1$ 轮，前 $i-1$ 人的胜利者（我们叫他 W_prev）会和勇士 $i$ 对战。我们要计算新胜利者出手势 j 的概率。新胜利者出手势 j 有两种可能：
1. W_prev 原本就出手势 j，并且他赢了勇士 $i$ 。
  - W_prev 出 j 的概率是 dp_prefix[i-1][j]。
  - 他要赢，勇士 $i$ 必须出被 j 克制的手势 (j+1)%3，或者也出 j（此时 W_prev 编号小，获胜）。
  - 所以这部分的概率是 dp_prefix[i-1][j] * (prob[i][j] + prob[i][(j+1)%3])。
2. 勇士 $i$ 出手势 j，并且他赢了 W_prev。
  - 勇士 $i$ 出 j 的概率是 prob[i][j]。
  - 他要赢，W_prev 必须出被 j 克制的手势 (j+1)%3。
  - W_prev 出 (j+1)%3 的概率是 dp_prefix[i-1][(j+1)%3]。
  - 所以这部分的概率是 prob[i][j] * dp_prefix[i-1][(j+1)%3]。

把它们加起来，就是我们的转移方程啦！

dp\_prefix[i][j] = dp\_prefix[i-1][j] \cdot (prob[i][j] + prob[i][(j+1)\%3]) + prob[i][j] \cdot dp\_prefix[i-1][(j+1)\%3]

后缀DP：`dp_suffix[i][j]`

现在我们从后往前看。定义 dp_suffix[i][j] 为：假设在第 i-2 轮结束后，擂主已经决出且他的手势是 j，那么他能够成功守擂，击败所有从 i 到 n 的挑战者的概率是多少。

基础 (Base Case): dp_suffix[n+1][j] = 1。因为已经没有挑战者了，擂主当然100%获胜啦！
转移 (Transition): 如何从 dp_suffix[i+1] 推导出 dp_suffix[i] 呢？手持 j 的擂主，要面对挑战者 i。他必须先赢下这一局，然后继续面对 i+1 到 n 的挑战。
- 他赢下挑战者 i 的概率是：勇士 $i$ 出被 j 克制的手势 (j+1)%3 或与 j 相同的手势。概率为 prob[i][j] + prob[i][(j+1)%3]。
- 赢了之后，他（手势仍为 j）继续守擂并最终获胜的概率是 dp_suffix[i+1][j]。

两者是连续发生的事件，所以概率相乘：

dp\_suffix[i][j] = dp\_suffix[i+1][j] \cdot (prob[i][j] + prob[i][(j+1)\%3])

整合答案：计算每个人的获胜概率！

有了前后缀DP数组，我们就可以计算每个勇士 $i$ 的总获胜概率了！

对于勇士 $i$ (且 $i>1, i<n$ )：

他选择手势 j 的概率是 prob[i][j]。
他要用手势 j 击败前 $i-1$ 人的胜利者。这意味着前 $i-1$ 人的胜利者必须出手势 (j+1)%3。这个事件的概率是 dp_prefix[i-1][(j+1)%3]。
获胜后，他作为手持 j 的新擂主，必须击败 $i+1, \dots, n$ 的所有挑战者。这个事件的概率是 dp_suffix[i+1][j]。

把这三部分乘起来，再对所有可能的 j (0, 1, 2) 求和，就是勇士 $i$ 的总获胜概率！

P(i \text{ wins}) = \sum_{j=0}^{2} prob[i][j] \cdot dp\_prefix[i-1][(j+1)\%3] \cdot dp\_suffix[i+1][j]

特殊情况处理喵~

勇士1: 他是最初的擂主之一，没有“前缀”对手。他的获胜条件是：选定一个手势 j，然后一路击败 $2, 3, \dots, n$ 。这正好是 dp_suffix[2][j] 的定义！ $P(1 \text{ wins}) = \sum_{j=0}^{2} prob[1][j] \cdot dp\_suffix[2][j]$
勇士n: 他是最后的挑战者，没有“后缀”对手。他的获胜条件是：选定一个手势 j，并击败从 $1, \dots, n-1$ 中决出的胜利者。 $P(n \text{ wins}) = \sum_{j=0}^{2} prob[n][j] \cdot dp\_prefix[n-1][(j+1)\%3]$

现在，我们已经有了完整的蓝图，可以开始写代码了，冲呀！

代码实现，看我的爪子多灵活！

cpp

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

// 定义模数
const int MOD = 998244353;

// 快速幂函数，用于计算模逆元
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模逆元函数
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // prob[i][j]: 勇士i选择手势j的概率
    // 0: 石头, 1: 剪刀, 2: 布
    vector<vector<long long>> prob(n + 1, vector<long long>(3));
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        long long total_options = 0;
        for (char c : s) {
            if (c == '1') {
                total_options++;
            }
        }
        long long inv_total = modInverse(total_options);
        if (s[0] == '1') prob[i][0] = inv_total; // 石头
        if (s[2] == '1') prob[i][1] = inv_total; // 剪刀
        if (s[1] == '1') prob[i][2] = inv_total; // 布
    }

    // --- 前缀DP ---
    // dp_prefix[i][j]: 前i个勇士中，胜利者出手势j的概率
    vector<vector<long long>> dp_prefix(n + 1, vector<long long>(3, 0));
    
    // 基础情况：勇士1
    for (int j = 0; j < 3; ++j) {
        dp_prefix[1][j] = prob[1][j];
    }

    // 递推计算
    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j < 3; ++j) {
            // j 克制 (j+1)%3
            int beaten_hand = (j + 1) % 3;
            
            // 情况1: 前i-1的胜利者出j，并战胜了勇士i
            long long prev_winner_wins = (dp_prefix[i - 1][j] * (prob[i][j] + prob[i][beaten_hand])) % MOD;
            
            // 情况2: 勇士i出j，并战胜了前i-1的胜利者
            long long current_challenger_wins = (prob[i][j] * dp_prefix[i - 1][beaten_hand]) % MOD;

            dp_prefix[i][j] = (prev_winner_wins + current_challenger_wins) % MOD;
        }
    }

    // --- 后缀DP ---
    // dp_suffix[i][j]: 一个手持j的擂主，能击败i到n所有挑战者的概率
    vector<vector<long long>> dp_suffix(n + 2, vector<long long>(3, 0));

    // 基础情况：没有挑战者了
    for (int j = 0; j < 3; ++j) {
        dp_suffix[n + 1][j] = 1;
    }
    
    // 递推计算
    for (int i = n; i >= 1; --i) {
        for (int j = 0; j < 3; ++j) {
            // j 克制 (j+1)%3
            int beaten_hand = (j + 1) % 3;
            
            // 擂主(手持j)战胜挑战者i的概率
            long long win_prob = (prob[i][j] + prob[i][beaten_hand]) % MOD;
            
            dp_suffix[i][j] = (dp_suffix[i + 1][j] * win_prob) % MOD;
        }
    }

    // --- 计算最终答案 ---
    for (int i = 1; i <= n; ++i) {
        long long final_ans = 0;
        if (i == 1) {
            // 勇士1的特殊情况
            for (int j = 0; j < 3; ++j) {
                final_ans = (final_ans + prob[1][j] * dp_suffix[2][j]) % MOD;
            }
        } else if (i == n) {
            // 勇士n的特殊情况
            for (int j = 0; j < 3; ++j) {
                int beaten_hand = (j + 1) % 3;
                final_ans = (final_ans + prob[n][j] * dp_prefix[n - 1][beaten_hand]) % MOD;
            }
        } else {
            // 一般情况
            for (int j = 0; j < 3; ++j) {
                int beaten_hand = (j + 1) % 3;
                long long term = (prob[i][j] * dp_prefix[i - 1][beaten_hand]) % MOD;
                term = (term * dp_suffix[i + 1][j]) % MOD;
                final_ans = (final_ans + term) % MOD;
            }
        }
        cout << final_ans << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

复杂度分析，一点也不难算的啦~

时间复杂度: $O(N)$
- 预处理每个人的出手概率需要遍历输入，总共是 $O(N)$ 。
- 前缀DP的计算，有一个从 $2$ 到 $n$ 的循环，内部是常数次（3次）运算，所以是 $O(N)$ 。
- 后缀DP的计算，有一个从 $n$ 到 $1$ 的循环，内部也是常数次运算，所以是 $O(N)$ 。
- 最后计算每个人的答案，有一个从 $1$ 到 $n$ 的循环，内部还是常数次运算，所以也是 $O(N)$ 。
- 总的时间复杂度就是 $O(N) + O(N) + O(N) = O(N)$ ，非常高效！
空间复杂度: $O(N)$
- 我们需要存储每个人的出手概率 prob，大小为 $O(N)$ 。
- dp_prefix 和 dp_suffix 两个数组，每个都需要 $O(N)$ 的空间。
- 所以总的空间复杂度是 $O(N)$ 。

知识点总结，快拿小本本记下来喵！

概率DP: 当问题涉及到概率和状态转移时，动态规划是一个强大的工具。关键是正确定义状态，表示某个事件发生的概率。
前后缀DP: 对于一个序列问题，如果第 $i$ 个元素的状态只与它前面的元素（前缀）和后面的元素（后缀）有关，那么可以分别计算前缀信息和后缀信息，最后再组合起来。这是一种解耦的绝妙思想！
模块化思维: 将一个复杂问题（某人获胜）分解成几个更简单的、独立的子问题（挑战成功、守擂成功），是解决难题的通用策略。
巧妙的状态定义: 在这道题里，通过一个非标准的映射（0=石, 1=剪, 2=布），我们得到了一个非常简洁的克制关系 j 克制 (j+1)%3，大大简化了DP转移方程。有时候，换个角度看问题，世界会变得更简单，喵~
模运算: 在计算概率时，除法要用乘以模逆元来代替。费马小定理是求模逆元的好帮手，但前提是模数必须为质数。

希望这篇题解能帮到你，Master！如果还有不懂的地方，随时可以再来问我哦，喵~

游戏 - 题解 ​

标签与难度 ​

喵？是新游戏！题目大意喵~ ​

解题思路分析，跟着我的思路来喵！ ​

核心思想：拆解胜利之路 ​

手势的奇妙映射，喵~ ​

前缀DP：dp_prefix[i][j] ​

后缀DP：dp_suffix[i][j] ​

整合答案：计算每个人的获胜概率！ ​

代码实现，看我的爪子多灵活！ ​

复杂度分析，一点也不难算的啦~ ​

知识点总结，快拿小本本记下来喵！ ​