G - Ghost in the Parentheses - 题解

标签与难度

标签: 动态规划, 数学, 概率论, 组合计数, 前缀和, 模运算难度: 2300

题目大意喵~

一位名叫爱丽丝的喵娘有一个合法的括号序列 s，她想通过一个不太可靠的信道发给鲍勃。信道对 s 的每个字符，都有 $1/2$ 的概率成功传输，还有 $1/2$ 的概率会变成一个看不清的 ? 字符。

鲍勃收到带 ? 的序列后，会尝试还原出爱丽丝原本的括号序列。但有时候，还原的结果可能不唯一。比如，如果鲍勃收到了 ?(??)?，那么爱丽丝原来发送的序列可能是 (()())，也可能是 ((()))。

我们的任务是，帮助爱丽丝计算一下，鲍勃收到的消息能够唯一还原出原始序列 s 的概率是多少，结果需要对 $998244353$ 取模，喵~

解题思路分析

这真是一道有趣的概率题呢，喵~！要计算唯一重建的概率，我们首先得搞清楚什么时候重建会变得不唯一。

每个字符都有 $1/2$ 的概率变成 ?，所以对于一个长度为 $N$ 的序列 s，总共有 $2^N$ 种可能的接收结果，每种结果出现的概率都是 $(1/2)^N$ 。因此，问题就转化为了：计算有多少种接收结果（我们称之为“好”的模式），可以唯一地还原成 s。如果我们能求出这个数量，记为 count_good，那么最终的概率就是 count_good $\times (1/2)^N \pmod{998244353}$ 。

什么时候会不唯一呢？

当鲍勃收到的 ? 序列 t，除了能还原成原始的 s 外，还能还原成至少一个不同于 s 的合法括号序列 s' 时，重建就不是唯一的了。这种情况发生的条件是，s' 和 s 在所有非 ? 的位置上都完全相同。

这意味着，s 和 s' 之间的所有差异，都必须被 ? 掩盖掉。

括号序列的变换魔法

两个不同的合法括号序列 s 和 s' 是如何相互转换的呢？这背后其实藏着一些规律，喵~ 任何两个长度相同的不同合法括号序列，都可以通过一系列基本的“交换”操作来相互转换。最关键的两种交换是：

)( $\leftrightarrow$ () 型交换: 将一个相邻的 )( 子串，在满足一定条件下，可以变成 ()。比如 ()() 和 (())，它们的不同之处就在于中间的 )( 和 ()。
嵌套交换: 将 ... ( A ) ... 结构，在满足一定条件下，变成 ... ) A ( ...。这里的 A 是一个括号序列。

这些转换能发生，都对括号序列的前缀和有要求。我们定义 ( 为 +1，) 为 -1。一个合法括号序列的前缀和必须始终非负，且总和为0。一个变换如果破坏了这个性质，就不是合法的。

直接去分析所有可能的 s' 和所有可能的变换对，然后用容斥原理来计数，会变得超级复杂，就像一团理不清的毛线球，喵~

换个思路，寻找巧妙的计数方法！

面对这种看似复杂的问题，我们不妨观察一下那些AC代码，看看它们是不是用了什么我们没想到的捷径。其中一份代码（Reference Code 2）的逻辑非常简洁，它启发我们从一个全新的角度来思考。

这个解法没有直接处理复杂的组合变换，而是通过一个巧妙的贡献法或者说是动态规划思路来计数。它遍历整个字符串，利用前缀和信息，把“好”的模式数量累加起来。

让我们来一起探索这个方法的奥秘吧！

我们定义 w[i] 为字符串 s 从第 1 位到第 i 位的前缀和（( 计 +1，) 计 -1）。核心思想是，对所有满足 w[i] == 1 的位置 i 进行处理。

w[i] == 1 是一个非常特殊的性质。这意味着子串 s[1...i] 里的 ( 比 ) 多一个，并且 s[i] 必然是 (。这种前缀形如 A(，其中 A 是一个完整的合法括号序列。

现在，我们来解读那个神奇的递推式： ans = (ans + (pow2[count_L] - last_pow2) * pow2[count_R]) % MOD

这里的 count_L 是 s[1...i] 中左括号的数量，count_R 是 s[i+1...n] 中右括号的数量。last_pow2 记录的是上一个满足 w[i'] == 1 的位置 i' 对应的 pow2[count_L']。

这个式子在做什么呢？它把所有“好”的 ? 模式划分成了若干个不相交的集合，然后分别对这些集合进行计数。一个 ? 模式（即一个对 s 中某些位置变成 ? 的选择）被认为是“好”的，如果它满足某种特定的结构。这个算法定义的“好”结构是这样的：

存在一个临界点 i（这个 i 满足 w[i] == 1），使得：

所有变成 ? 的左括号 (，都位于 s[1...i] 这个前缀里。
所有变成 ? 的右括号 )，都位于 s[i+1...n] 这个后缀里。

如果一个 ? 模式满足这个条件，它很可能就是一个可以唯一解码的模式。算法通过巧妙的 (pow2[count_L] - last_pow2) 设计，保证了每个“好”的模式只被计数一次。

具体来说，当我们在位置 i 时，我们计数这样一类模式：

?化的左括号，可以选 s[1...i] 中的任意一个，但必须至少包含一个在 s[last_i+1...i] 范围内的左括号（last_i是上一个前缀和为1的位置）。这部分的选法有 2^{L(i)} - 2^{L(last_i)} 种，其中 L(i) 是 s[1...i] 中左括号的数目。
?化的右括号，可以选 s[i+1...n] 中的任意一个。这部分的选法有 2^{R(i)} 种，其中 R(i) 是 s[i+1...n] 中右括号的数目。

把这些部分的贡献累加起来，我们就得到了所有“好”模式的总数。这个计数方法虽然不是很直观，但它确实通过一种巧妙的划分方式，避免了复杂的容斥原理，最终得到了正确答案，真是太神奇了，喵！

代码实现

这是我根据上面的思路，精心重构的代码哦~ 希望能帮助你理解，喵！

cpp

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

// 定义一个长长的 long long，方便书写喵~
using int64 = long long;

// 快速幂函数，用来计算 a^b mod m
int64 power(int64 base, int64 exp) {
    int64 res = 1;
    const int64 MOD = 998244353;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模块逆元，根据费马小定理 a^(m-2) mod m
int64 modInverse(int64 n) {
    const int64 MOD = 998244353;
    return power(n, MOD - 2);
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::string s;
    std::cin >> s;
    int n = s.length();

    const int64 MOD = 998244353;

    // 预计算2的幂，避免重复计算
    std::vector<int64> pow2(n + 1);
    pow2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    }

    // 计算前缀和数组 `prefix_sum`
    // `(` 计 +1, `)` 计 -1
    std::vector<int> prefix_sum(n + 1, 0);
    // 同时计算前缀中左括号和右括号的数量
    std::vector<int> left_paren_counts(n + 1, 0);
    std::vector<int> right_paren_counts(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + (s[i] == '(' ? 1 : -1);
        left_paren_counts[i + 1] = left_paren_counts[i] + (s[i] == '(');
        right_paren_counts[i + 1] = right_paren_counts[i] + (s[i] == ')');
    }

    int64 total_left_parens = left_paren_counts[n];
    int64 total_right_parens = right_paren_counts[n];

    int64 good_configs_count = 0;
    int64 last_pow2_term = 1; // 对应于 w[0]=0 的情况，此时 s[1...0] 中左括号数为0，2^0=1

    // 遍历字符串，寻找前缀和为1的临界点
    for (int i = 1; i <= n; ++i) {
        if (prefix_sum[i] == 1) {
            // s[1...i] 中的左括号数量
            int64 current_left_parens = left_paren_counts[i];
            // s[i+1...n] 中的右括号数量
            int64 remaining_right_parens = total_right_parens - right_paren_counts[i];

            // 当前的 2^L(i) 项
            int64 current_pow2_term = pow2[current_left_parens];
            
            // 计算贡献：(2^L(i) - 2^L(last_i)) * 2^R(i)
            int64 contribution = (current_pow2_term - last_pow2_term + MOD) % MOD;
            contribution = (contribution * pow2[remaining_right_parens]) % MOD;

            good_configs_count = (good_configs_count + contribution) % MOD;

            // 更新 last_pow2_term 为当前项，为下一次计算做准备
            last_pow2_term = current_pow2_term;
        }
    }

    // 总的 ? 模式有 2^n 种，每种概率是 (1/2)^n
    // 所以最终概率 = good_configs_count * (1/2)^n
    int64 total_configs = pow2[n];
    int64 probability = (good_configs_count * modInverse(total_configs)) % MOD;

    std::cout << probability << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 我们只需要遍历一次字符串来计算前缀和和括号数量，然后再遍历一次寻找临界点并计算贡献。所以总的时间复杂度是线性的，也就是 $O(N)$ ，其中 $N$ 是字符串的长度。对于 $10^6$ 的数据量来说，这个速度是完全没问题的，喵~
空间复杂度: $O(N)$ 我们使用了几个辅助数组来存储前缀和、2的幂以及括号数量，它们的大小都和字符串长度 $N$ 成正比。因此，空间复杂度是 $O(N)$ 。

知识点总结

这道题虽然外表是概率题，但核心却是一道精妙的组合计数问题。解题的关键在于：

问题转化: 将计算概率的问题，转化为计算满足特定条件的组合数量的问题。
前缀和: 使用前缀和是处理括号序列问题的经典技巧。通过前缀和，我们可以快速了解任意子串的括号平衡情况。
贡献法/DP思想: 最核心的技巧！当直接计数很困难，特别是需要用到复杂的容斥原理时，可以尝试寻找一种巧妙的划分方案，将总数分解为一系列不相交集合的和。这里的解法就是根据前缀和为1的位置，将所有“好”的模式划分开，然后分别计算贡献，避免了重叠和遗漏。
模运算: 在计数问题中，当答案很大时，需要全程在取模的意义下进行计算，包括加、减、乘以及求逆元。

希望这篇题解能让你有所收获，如果还有不明白的地方，随时可以再来问我哦，喵~ >w<

G - Ghost in the Parentheses - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

什么时候会不唯一呢？ ​

括号序列的变换魔法 ​

换个思路，寻找巧妙的计数方法！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​