题解 P7263 【Something Comforting】
囧仙
2021-01-10 23:10:09
## 题目大意
- 有一个随机括号序列生成器，首先会随机生成一个**不一定合法的**长度为 $2\times n$ 的由 $n$ 个左括号和 $n$ 个右括号组成的序列。然后顺序枚举，每碰到一个不合法的右括号就找到它最右侧的合法的左括号，并翻转这段区间。
- 现在给出有一个长度为 $2\times n$ 的合法的括号序列，询问随机括号生成器生成出它的概率为多少。结果对 $998244353$ 取模。
## 题解
考虑一个非常重要的结论：**最终序列中一个连续的合法的括号序列，最多只由一次翻转得到**。并且不合法的右括号左侧的括号序列必定是合法的。
补充一下从头开始的括号括号序列的定义。这个序列并不会包含于任何一个括号序列之中。更形式一些的说法，它左侧的所有括号可以组成一个合法的括号序列。
考虑根据题目给出的代码，左括号记为 $+1$ ，右括号记为 $-1$ ，计算其前缀和。
$$\verb!())))((()(()!=\{1,0,-1,-2,-3,-2,-1,0,-1,0,1,0\}$$
到第三个括号的时候，它的前缀值为 $-1$ 。于是我们要找到它右侧第一个合法的左括号（也就是第一个前缀值为 $0$ 的括号，对应于第 $8$ 个）然后进行翻转。
经过观察，我们能够发现，反转的区间**必定中间的值都不大于 $0$** 。因此，最终结果里一段从头开始的合法括号序列最终由不超过一次翻转得到。
这个结论说明了什么呢？**一个从头开始的合法括号区间要么翻转一次，要么不翻转**。
考虑初始生成的括号序列有多少种。假设原先 $2\times n$ 个括号都是左括号，我们选择其中 $n$ 个进行翻转后就是一个满足初步要求的初始序列了，因此总方案数为从 $2n$ 个数中挑选 $n$ 个的结果，即为 $C(2n,n)$ 。
然后最终括号序列之前可能对应多少种括号序列呢？这可以用乘法原理得到。每个从头开始的括号序列都有翻转或者不翻转两种情况，于是最终的答案为：
$$\frac{2^t}{C(2n,n)}$$
其中 $t$ 是从头开始的括号序列的总个数。总时间复杂度为 $\mathcal O(\log_2 n+n)$ 。
## 参考代码
```cpp
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
int qread(){
int w=1,c,ret;
while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
return ret*w;
}
char rdc(){
char c; while(!isgraph(c=getchar())); return c;
}
const int MOD=998244353;
const int MAXN =5e5+3;
int n,w,s,F[MAXN];
int pwr(int a,int b){
int r=1; while(b){
if(b&1) r=1ll*r*a%MOD; b>>=1,a=1ll*a*a%MOD;
}
return r;
}
int main(){
n=qread(),F[0]=1; up(1,2*n,i){
char c=rdc(); s+=(c=='('?1:-1),F[i]=1ll*F[i-1]*i%MOD; if(s==0) ++w;
}
printf("%lld\n",2ll*pwr(F[2*n],MOD-2)*F[n]%MOD*F[n]%MOD*pwr(2,w-1)%MOD);
return 0;
}
/*
()((()))
*/
```