正題

題目鏈接: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]括号【组合数学】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。