很有意思的组合计数加容斥。

Solution

• $K=0$

就是经典括号匹配问题，开个栈模拟一下即可。

• $K=1$

显然可以 $O(n^2)$ 枚举子串，但这样复杂度太高。

考虑拆开找贡献，对于下标为 $i$ 的左括号，设它匹配的右括号下标为 $j$ (特别的，没有匹配时 $j=n+1$ )。

那么易证，这个左括号对所有 $i\le r＜ j$ 且 $1\le l\le i$ 的区间都有 1 的贡献，总贡献即为 $i\times(j-i)$ 。

右括号同理，因此可以 $O(n)$ 计算。

• $K>1$

套用 $K=1$ 时的计算方法，找贡献。

我们发现对于一个 $K$ 级偏值的字符串，只会对包含它的母串的 $K+1$ 级偏值造成贡献。

还是假设以下一个下标为 $i$ 的左括号，设它匹配的右括号下标为 $j$ 。

那么我们就要找到所有这样的 $K$ 个区间层层嵌套的区间组。

将 $K$ 个区间的左右端点抽象以下扔到数轴上就是：

$i$ 左边为值域在 $[1,i]$ ，长度为 $K$ 的不降序列。

$i$ 右边为值域在 $[i,n]$ ，长度为 $K$ 的不降序列，其中第一个元素要小于 $j$ 。

发现 $i$ 左边的好处理，等价于将 $K$ 个数装进 $i$ 个箱子里，允许空箱子，经典组合问题，答案为 $\dbinom{K+i-1}{i-1}$ 。

右边不是很好处理，但是看一会发现可以容斥。

强制使第一个元素大于等于 $j$ ，那么就是值域在 $[j,n]$ ，长度为 $K$ 的不降序列，答案为 $\dbinom{K+n-j}{n-j}$ 。

最终总贡献就是 $\dbinom{K+i-1}{i-1}\times \left(\dbinom{K+n-i}{n-i}-\dbinom{K+n-j}{n-j}\right)$ 。

右括号同理。

Code

#include<bits/stdc++.h>
#define orz puts("%%%wyy332623");
#define N 2000005
#define int long long
using namespace std;

inline int read(){
    int x=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*w;
}

const int mod = 998244353;
int n,k,ans;
int fac[N],ifac[N],p[N];
char ch[N];
stack<int> s;

int qpow(int x,int k){
    int res=1;
    while(k){
        if(k&1) res=res*x%mod;
        x=x*x%mod;k>>=1;
    }
    return res;
}
void init(){
    fac[0]=ifac[0]=1;
    for(int i=1;i<=2000000;++i) fac[i]=fac[i-1]*i%mod;
    ifac[2000000]=qpow(fac[2000000],mod-2);
    for(int i=1999999;i>=1;--i) ifac[i]=ifac[i+1]*(i+1)%mod;
}
int C(int x,int y){return fac[x]*ifac[y]%mod*ifac[x-y]%mod;}

signed main(){
    init();
    n=read();k=read();
    scanf("%s",ch+1);
    for(int i=1;i<=n;++i) if(ch[i]=='(') p[i]=n+1;
    for(int i=1;i<=n;++i) 
        if(ch[i]=='(')s.push(i);
        else {
            if(s.empty()) continue;
            p[s.top()]=i,p[i]=s.top(),s.pop();
        }
    for(int i=1;i<=n;++i)
        if(ch[i]=='(') ans=(ans+C(k+i-1,i-1)*(C(k+n-i,n-i)-C(n-p[i]+k,n-p[i])+mod)%mod)%mod;
        else ans=(ans+C(k+n-i,n-i)*(C(k+i-1,i-1)-C(k+p[i]-1,p[i]-1)+mod))%mod;
    printf("%lld\n",ans);
    return 0;
}