P7044 「MCOI-03」括号 题解
ChengJY_
·
·
题解
很有意思的组合计数加容斥。
Solution
就是经典括号匹配问题，开个栈模拟一下即可。
显然可以 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 级偏值的字符串，只会对包含它的母串的 K+1 级偏值造成贡献。
还是假设以下一个下标为 i 的左括号，设它匹配的右括号下标为 j 。
那么我们就要找到所有这样的 K 个区间层层嵌套的区间组。
将 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
```cpp
#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;
}
```