vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

题解 P7263 【Something Comforting】

posted on 2021-01-10 22:37:23 | under 题解 |

我们从所给代码中的变量 $sum$ 入手,考虑 $sum$ 与 $i$ 的关系。令 $sum_{i}$ 表示遍历到第 $i$ 个位置时 $sum$ 的大小,则有 $sum_{i}=sum_{i-1}+1$ 或 $sum_{i}=sum_{i-1}-1$。

假设我们在执行代码时取反了 $[i,j]$ 这段区间,那么在取反之前一定有 $sum_{i-1}=0,sum_{i}=-1,sum_{i+1,i+2…,j-1}\le -1,sum_{j}=0$。不难看出取反 $[i,j]$ 这段区间相当于把 $sum_{i…j}$ 都取反。转化一下,区间 $[i,j]$ 能由某种括号序列取反得到,当且仅当 $sum_{i-1}=0,sum_{j}=0$ 且 $\forall k\in [i,j-1],sum_{k} \not= 0$。每有这样的一段区间,所给代码中合法的 $arr$ 序列的方案数就会乘 $2$。满足条件的区间数量就是 $sum$ 数组中 $0$ 的个数,设为 $cnt$,合法的方案数就是 $2^{cnt}$,算概率还需要除以总的方案数。总方案数也不难算,相当于从 $2n$ 个位置里无顺序地选出 $n$ 个位置作为 $1$,即 $C(2n,n)$。最终的答案就是 $\frac{2^{cnt}}{C(2n,n)}$ 对 $998244353$ 取模的结果。

代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

const int yrz=998244353;

int ksm(int x,int y){
    if(y==0) return 1;
    int k=ksm(x,y/2);
    k=1ll*k*k%yrz;
    if(y&1) k=1ll*k*x%yrz;
    return k;
}

int main(){
    int n,sum=0,cnt=0,jc1=1,jc2=1;
    cin>>n;
    fo(i,1,n) jc1=1ll*jc1*i%yrz;
    fo(i,n+1,2*n) jc2=1ll*jc2*i%yrz; 
    char ch=getchar();while(ch!='('&&ch!=')') ch=getchar();
    fo(i,1,n*2){    
        if(ch=='(') ++sum;
        else --sum;
        if(sum==0) ++cnt;
        ch=getchar();
    }
    cout<<1ll*ksm(2,cnt)*ksm(1ll*jc2*ksm(jc1,yrz-2)%yrz,yrz-2)%yrz;
    return 0;
}