洛谷P7044 「MCOI-03」括号（栈括号的贡献 组合数经典问题）

题目

思路来源

P7044 「MCOI-03」括号 题解 - 洛谷专栏

题解

统计一对括号的贡献，对于一个左括号i，找到其右第一个匹配的括号的位置j

这样对于不包含这个(i,j)对的区间[l,r]（1<=l<=i，i<=r<j）来说，(i,j)对都是有贡献的，这样的区间数是i*(j-i)

再考虑k次嵌套的组合意义，

记第一次选的右端点x，

由于i<=x，且i后续非严格递减，x后续非严格递增，不妨拆开看成两个序列l、r

k=1时，需要选长度为1的序列l[]、r[]，满足l[1]∈[1,i]，r[1]<j

k>1时，需要选长度为k的序列l[]、r[]，满足l[j]∈[1,i]，l[j]<=l[j+1]，r[1]<j，r[j]<=r[j+1]

l序列是好求的，这等价于在i个数每个数出现xi(xi>=0)次，满足，方案数是

r序列，由于有r[1]<j的限制，可以用在[i,n]里任取减去在[j,n]里任取，方案数是

代入k=1，其实发现也成立

因为算的是匹配不上的贡献，所以需要对每个左括号和右括号分别统计

代码

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)

const int N=2e6+10,mod=998244353;
int n,k,Finv[N],fac[N],inv[N],p[N];
int stk[N],c,ans;
char s[N];
int modpow(int x,int n,int mod){
	int res=1;
	for(;n;x=1ll*x*x%mod,n>>=1)
	if(n&1)res=1ll*res*x%mod;
	return res;
}
void init(int n){ //n<N
    inv[1]=1;
    for(int i=2;i<=n;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	fac[0]=Finv[0]=1;
	for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod,Finv[i]=1ll*Finv[i-1]*inv[i]%mod;
}
int C(int n,int m){
	if(m<0||m>n)return 0;
	return 1ll*fac[n]*Finv[n-m]%mod*Finv[m]%mod;
}
int main(){
    init(N-5);
    sci(n),sci(k);
    scanf("%s",s+1);
    rep(i,1,n){
        if(s[i]=='(')p[i]=n+1;
        //else p[i]=0;
    }
    rep(i,1,n){
        if(s[i]=='(')stk[++c]=i;
        else{
            if(!c)continue;
            int v=stk[c--];
            p[v]=i;p[i]=v;
        }
    }
    rep(i,1,n){
        if(s[i]=='(')ans=(ans+1ll*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+1ll*C(k+n-i,n-i)*(C(k+i-1,i-1)-C(k+p[i]-1,p[i]-1)+mod))%mod;
    }
    pte(ans);
    return 0;
}