题解似乎清一色是同一个做法,这里给一个容斥的做法。
首先枚举一个位置 \(i\),设 \([1,i]\) 的左括号个数为 \(p\),\([i + 1,n]\) 的右括号个数为 \(q\),那么以 \(i\) 这个位置为分界点的合法括号数有 \(\sum_{i = 1}^{\min(p,q)} C_p^i C_q^i\) 个。通过范德蒙德卷积我们可以知道这个的值为 \(C_{p + q}^p - 1\)。
然后枚举 \(i\) 作为分界点求和就行了吗?
算一下样例发现这并不对,原因是会算重,手玩一下容易发现,上面的答案再减去对于一个分界点 \(j\),计算 \([1,j - 1]\) 和 \([j + 1,n]\) 之间的贡献即可。
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,p=1e9+7;
string s;
int n,pre[N],suf[N],fac[N],inv[N],ans=0;
int qpow(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
void init(int lim) {
fac[0]=inv[0]=1;
for(int i=1; i<=lim; i++) fac[i]=fac[i-1]*i%p;
inv[lim]=qpow(fac[lim],p-2);
for(int i=lim-1; i>=1; i--) inv[i]=inv[i+1]*(i+1)%p;
}
int C(int n,int m) {
if(n<0||m<0||n<m) return 0;
return fac[n]*inv[m]%p*inv[n-m]%p;
}
signed main() {
cin>>s;n=s.size();s=' '+s;
init(n);
for(int i=1; i<=n; i++) pre[i]=pre[i-1]+(s[i]=='(');
for(int i=n; i>=1; i--) suf[i]=suf[i+1]+(s[i]==')');
for(int i=1; i<n; i++) ans=(ans+C(pre[i]+suf[i+1],pre[i])-1+p)%p;
for(int i=1; i<n-1; i++) ans=(ans-C(pre[i]+suf[i+2],pre[i])+1+p)%p;
cout<<ans;
return 0;
}
标签:分界点,suf,CF785D,int,题解,inv,ans
From: https://www.cnblogs.com/System-Error/p/18541488