题意:给你一个由'('和')'组成的字符串,问你有多少个子串,前半部分是由'('组成后半部分由')'组成

思路:枚举这个字符串中的所有'('左括号,它左边的所有'('左括号的个数为num1,它的右边的所有’)'右括号的个数为num2,

CF #404 (Div. 2) D. Anton and School - 2 (数论+范德蒙恒等式)-LMLPHP

根据范德蒙恒等式计算得出

代码:

#include <bits/stdc++.h>
#define ll long long
#define maxn 200000
#define mod 1000000007
using namespace std; ll jc[maxn+]; void get_jc()
{
jc[]=;
for(int i=;i<=maxn;i++)
{
jc[i]=(jc[i-]*i)%mod;
}
} ll qmod(ll a,ll b)
{
ll ans=;
while(b)
{
if(b%==)
{
ans=(ans*a)%mod;
}
b=b/;
a=(a*a)%mod;
}
return ans;
} ll get_C(ll m,ll n)
{
return (jc[m]*qmod((jc[m-n]*jc[n])%mod,mod-))%mod;
} int main()
{
string data;
int num1[maxn+],num2[maxn+];
get_jc();
while(cin>>data)
{
int p=;
for(int i=;i<data.length();i++)
{
if(data[i]=='(')
{
p++;
}
num1[i]=p;
}
p=;
ll ans=;
for(int i=data.length()-;i>=;i--)
{
if(data[i]==')')
{
p++;
}
num2[i]=p;
}
for(int i=;i<data.length();i++)
{
if(data[i]=='(')
{
ans=(ans+get_C(num1[i]+num2[i]-,num2[i]-))%mod;
}
}
cout<<ans<<endl;
}
return ;
}
05-06 04:10