当前位置：首页 > news >正文

D. Anton and School - 2

news 2025/9/13 8:44:33

范德蒙德恒等式

$\sum_{i=0}^{n}\binom{n}{i}*\binom{m}{x-i} = \binom{n+m}{x}$

考虑统计每一个右括号位置的贡献，也就是每个右括号作为右边起点的贡献

$\sum_{i=1}^{r}\binom{l}{i}\binom{r-1}{i-1}= \sum_{i=1}^{r}\binom{l}{i}\binom{r-1}{r-i} = \binom{l+r-1}{r}$

其中i=0的时候，r-1<r-0,故i=0时贡献为0，直接套用恒等式不会有影响

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
# define mod 1000000007
ll fac[1000000+10],inv[1000000+10];
ll qp(ll base, ll pow)
{ll ans=1;while(pow){if(pow&1)ans=ans*base%mod;pow>>=1;base=base*base%mod;}return ans;
}
void init()
{fac[0]=1;for(int i=1;i<=1000000;i++){fac[i]=fac[i-1]*(ll)i%mod;}inv[1000000]=qp(fac[1000000],mod-2);for(int i=1000000-1;i>=0;i--){inv[i]=(ll)(i+1)*inv[i+1]%mod;}
}
ll getc(int x,int y)
{if(x<y)return 0;return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int l[200000+10],r[200000+10];
int main()
{init();string s;cin>>s;s=" "+s;for(int i=1;i<s.length();i++){l[i]+=l[i-1];l[i]+=(s[i]=='(');}for(int i=s.length()-1;i>=1;i--){r[i]+=r[i+1];r[i]+=(s[i]==')');}ll ans=0;for(int i=2;i<s.length();i++){if(s[i]==')'){ans+=getc(r[i]+l[i]-1,r[i]);ans%=mod;}}cout<<ans;return 0;
}

查看全文

http://www.lryc.cn/news/132094.html