正题

题目链接:https://www.luogu.com.cn/problem/P7044?contestId=36089

---

题目大意

一个括号序列，0级偏值定义为其中不合法的括号数量。
$k$级偏值定义为它所有子串的$k-1$级偏值的和。
求这个括号序列的$k$级偏值。

---

解题思路

后文中我们定义$G(x,y)=C_{x+y-1}^y$

考虑每一对括号的贡献，不合法情况为只选择左括号或者只选择右括号。我们设他们为$[l,r]$，那么只包含左括号就是$L\in [1,l],R\in [l,r-1]$的区间。转换到$k$阶就是$G(l,k)$。

右边就不同了，我们观察一下每个阶时的值

r-3r-2r-1rr+1…

1	1	1	0	0
1	2	3	3	3
1	3	6	9	12

不难发现到后面$(x,y)$这个位置就是$G(x,y)-G(x-r+l-1,y)$

用组合数统计答案即可。

时间复杂度$O(n\log n)$（线性预处理逆元可以做到$O(n)$）

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #define ll long long using namespace std; const ll N=2e6+10,XJQ=998244353; ll n,k,ans,fac[N],inv[N]; char s[N];stack<int> S; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } ll G(ll n,ll m){if(n<=0||m<0)return 0;n=n+m-1;return fac[n]*inv[m]%XJQ*inv[n-m]%XJQ; } ll solve(ll l,ll r,bool op){ll ans=1;if(op)l=n-l+1,r=n-r+1,swap(l,r);ans=(G(r,k)-G(l-1,k)+XJQ)%XJQ;return ans; } int main() {scanf("%lld%lld",&n,&k);ll lim=max(n,k);fac[0]=inv[0]=1;for(ll i=1;i<=2*lim;i++){fac[i]=fac[i-1]*i%XJQ;inv[i]=power(fac[i],XJQ-2);}scanf("%s",s+1);for(ll i=1;i<=n;i++){if(s[i]=='(')S.push(i);else{if(!S.empty()){ans=(ans+solve(1,S.top(),0)*solve(S.top(),i-1,1)%XJQ)%XJQ;S.pop();}else ans=(ans+solve(1,i,0)*solve(i,n,1)%XJQ)%XJQ;}}while(!S.empty())S.pop();for(ll i=n;i>=1;i--){if(s[i]==')')S.push(i);else{if(!S.empty()){ans=(ans+solve(S.top(),n,1)*solve(i+1,S.top(),0)%XJQ)%XJQ;S.pop();}else ans=(ans+solve(1,i,0)*solve(i,n,1)%XJQ)%XJQ;}}printf("%lld",ans); }

总结

以上是生活随笔为你收集整理的P7044-[MCOI-03]括号【组合数学】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。