题解 P8003

dead_X · 2022-01-04 15:13:21 · 题解

前言

考场降智想到了性质但是没有考虑那一类情况，于是寄了。

思路

首先 n=2 的情况是平凡的，我们直接判掉就行了。

下文用“最后一段”指最右边的极长左括号段，我们考虑新加入的左括号：

在最后一段之前，例如 \texttt{(())(())}\to\texttt{(()}\color{red}\texttt{(}\color{black}\texttt{)(())}。

删除最后一段的一个括号，加入这个括号，显然仍然合法，因此不能插入。

加入最后一段，例如 \texttt{(())(())}\to\texttt{(())}\color{red}\texttt{(}\color{black}\texttt{(())} 或者 \texttt{(()())}\to\texttt{(()}\color{red}\texttt{(}\color{black}\texttt{())}。

如果删除倒数第二段的一个括号，加入这个括号仍然合法，那么不能插入，否则可以插入。

给出的例子中，第一个是合法的，而第二个是不合法的。

通过观察和验证不难发现这个条件等价于这段括号后左括号和右括号的数量不相等。

加入最后一段之后，但是右侧仍然存在一个右括号，例如 \texttt{(())(())}\to\texttt{(())(()}\color{red}\texttt{(}\color{black}\texttt{)}。

删除最后一段的一个括号，加入这个括号，显然仍然合法，因此不能插入。

加入末尾，例如 \texttt{(())(())}\to\texttt{(())(())}\color{red}\texttt{(}。

显然不可能选这个括号，于是还是合法，因此可以插入。

右括号是同理的，于是我们证明了只能在如上所述的地方插入新的括号的必要性。不难发现在最开始插入右括号和在最后插入左括号都没有意义，而剩下的情况中插入的括号要么只能形成 \texttt{((...()...))}，要么根本没有交集，因此充分性也可以证明。

计数是平凡的，设 f_i 为插入 i 个左括号的情况。

如果左括号只能在最后插入，那么 f_i=1。

如果左括号可以在最后或最后一段左括号插入，记最后一段左括号长度为 l，那么 f_i=\sum\limits_{j=0}^i\binom{l+i}{i}。

合并左括号和右括号的方案数即可，时间复杂度 O(n)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=998244353;
int qp(int x,int y)
{
    int res=1;
    for(int t=x; y; y>>=1,t=t*t%p) if(y&1) res=res*t%p;
    return res;
}
char s[1000003];
int fac[1000003],ifac[1000003];
int C(int n,int m)
{
    return fac[n]*ifac[m]%p*ifac[n-m]%p;
}
int A(int x,int y,int z)
{
    int res=0;
    if(x!=z) return 1;
    for(int i=0; i<=y; ++i)
        res=(res+C(x+i,i))%p; 
    return res;
}
int F[1000003],G[1000003];
signed main()
{
    const int N=1000000;
    fac[0]=ifac[0]=1;
    for(int i=1; i<=N; ++i) fac[i]=fac[i-1]*i%p;
    ifac[N]=qp(fac[N],p-2);
    for(int i=N-1; i>=1; --i) ifac[i]=ifac[i+1]*(i+1)%p;
    for(int T=read();T--;)
    {
        int n=read(),m=read();
        scanf("%s",s+1);
        if(n==2) printf("%lld\n",(m*(m-1)/2)%p*qp(2,m-n)%p);
        else
        {
            m-=n;
            int fir=1,lst=n,fc=0,lc=0,ffc=0,llc=0;
            while(s[fir]=='(') ++ffc,++fir;
            while(s[lst]==')') ++llc,--lst;
            while(s[fir]==')') ++fc,++fir;
            while(s[lst]=='(') ++lc,--lst;
            int ans=0;
            F[0]=G[0]=1;
            for(int i=1; i<=m; ++i) 
            {
                F[i]=F[i-1];
                if(fc==ffc) F[i]=(F[i]+C(fc+i,i))%p;
            }
            for(int i=1; i<=m; ++i) 
            {
                G[i]=G[i-1];
                if(lc==llc) G[i]=(G[i]+C(lc+i,i))%p;
            }
            for(int i=0; i<=m; ++i) ans=(ans+F[i]*G[m-i])%p;
            printf("%lld\n",ans);
        }
    }
    return 0;
}