2025牛客暑期多校训练营4 G Ghost in the Parentheses 题解记录

大致题意：给定一个合法的括号序列，经过变换以后，任意一个字符都有$\frac{1}{2}$独立的概率变成$?$。有多大的概率，使得原括号序列在变换以后，得到的新序列是唯一合法的？
解：
针对括号序列相关题，一般都可以设置$($为$+1$，$)$为$-1$。合法代表前缀和为$0$。要想新序列是唯一合法的，其只能被还原为原来的序列，并且左括号与右括号数量上要跟原来的保持一致。由此，只是几个$+1$和$-1$位置上调换。
要想唯一，如果调换过后是非法的，那么就说明只有原序列是合法的，进而推出唯一合法。考虑什么时候调换以后是非法的。
同类型的括号交换是没有意义的，只能交换不同类型的括号。如果一个形如$)\dots ($这样的子序列，在原先合法的情况下交换一定仍然是合法的，会出现多个合法性，不唯一；而对于$(\dots )$这样的，根据计算过的前缀和（高度），如果中间出现某个位置的$h_i\le 1$，交换过后这个位置的高度会$<0$，此时就是不合法、唯一的。关于高度问题，见此。定义$i$，$s_i{=}^{\prime }{(}^{\prime }$，其右边最近的$j$，满足$\exists k\in [i,j)，h_k\le 1$，$s_j{=}^{\prime }{)}^{\prime }$。对于$j$及其右边的$)$，即$su{f}_j$个右括号，不论它们是否变成问号，只要$i$位置上为括号，那么就是唯一的。因为这个位置不能变成右括号，只能是左括号。然后根据数量上守恒，右括号仍然是右括号。
同理对于$i$左边的左括号，这$pr{e}_{i-1}$个左括号如果变成问号，也是唯一的、不能变化的。如果右边的某个右括号跟左边某个左括号互换，那么就会导致中间$k$的位置高度出现负数，不合法。
由此，可以用类似单调栈的东西记录下每个左括号右边距离其最近的高度小于等于$1$的位置，然后再记录每个高度小于等于$1$的位置其右边最近的右括号的位置。

	vector<int> h(len + 1);vector<int> pre(len + 1), suf(len + 5);for (int i = 1; i <= len; i++) {h[i] = h[i - 1] + (s[i] == '(' ? 1 : -1);pre[i] = pre[i - 1] + (s[i] == '(' ? 1 : 0);}for (int i = len; i >= 1; i--) {suf[i] = suf[i + 1] + (s[i] == ')' ? 1 : 0);}int cnt = 0;vector<int> r0(len + 1);queue<int> q;for (int i = 1; i <= len; i++) {if (s[i] == '(') {q.push(i);}if (h[i] <= 1) {while (q.size()) {r0[q.front()] = i;q.pop();}}}vector<int> rn(len + 1);queue<int> qq;for (int i = 1; i <= len; i++) {if (h[i] <= 1) {qq.push(i);}if (s[i] == ')') {while (qq.size()) {rn[qq.front()] = i;qq.pop();}}}

然后开始计数。

	cnt = add(cnt, qp(2, suf[1], mod));for (int i = 1; i <= len; i++) {if (s[i] == '(') {int l = pre[i - 1];int temp = rn[r0[i]];if (temp == r0[i])temp++;int r = suf[temp];cnt = add(cnt, qp(2, l + r, mod));}}int inv2 = qp(2, mod - 2, mod);cout << mul(cnt, qp(inv2, len, mod)) << endl;

这里需要注意一个东西，如果某个高度小于等于$1$的位置本身就是右括号，那么这个位置就算交换了也是合法的，导致结果不唯一。所以此时计右括号数量的时候要$-1$。