codeforce 785 D. Anton and School

codeforce 785 D. Anton and School - 2

2024-03-02 08:58

文章标签 school codeforce anton 785

本文主要是介绍codeforce 785 D. Anton and School - 2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://codeforces.com/contest/785/problem/D
题意：给一堆括号，求有多少种规范的括号
假如说这样： $()($ $($ $())))$

考虑每个括号的贡献，假如现在考虑第一个红色括号的贡献：
他的前面有 $2$ 个 $($ ，后面有 $4$ 个 $)$
考虑只配对成1对：他的前面选 $0$ 个 $($ ，后面选 $1$ 个 $)$ ，那就是 $C_2^0*C_4^1$ 种情况
考虑只配对成2对：他的前面选 $1$ 个 $($ ，后面选 $2$ 个 $)$ ，那就是 $C_2^1*C_4^2$ 种情况
考虑只配对成3对：他的前面选 $2$ 个 $($ ，后面选 $3$ 个 $)$ ，那就是 $C_2^2*C_4^3$ 种情况
那么他的贡献就只有这么多了
而 $C_2^0*C_4^1+C_2^1*C_4^2+C_2^2*C_4^3$
也就是 $\sum_{i=0}^{k=min(n,m)}C_n^i*C_m^{i+1}$
而这种阔以有范德蒙恒等式简化

#include"bits/stdc++.h"
using namespace std;
const int maxn=2e5+5;
const int MOD=1e9+7;
char s[maxn];
int sum1[maxn],sum2[maxn];
long long fac[maxn]={1,1},inv[maxn]={1,1};
long long ksm(long long a,long long b,long long mod)
{long long res=1,base=a;while(b){if(b&1)res=(res*base)%mod;base=(base*base)%mod;b>>=1;}return res;
}
long long C(int n,int m)
{long long res=fac[n]*inv[m]%MOD;res=res*inv[n-m]%MOD;return res;
}
int main()
{for(int i=2;i<=200000;i++){fac[i]=(long long)i*fac[i-1]%MOD;inv[i]=(long long)inv[i-1]*ksm(i,MOD-2,MOD)%MOD;}
//    cout<<C(10,5)<<endl;while(cin>>s){memset(sum1,0,sizeof(sum1));memset(sum2,0,sizeof(sum2));int len=strlen(s);for(int i=1,j=len;i<=len;i++,j--){sum1[i]=sum1[i-1];if(s[i-1]=='(')sum1[i]++;sum2[j]=sum2[j+1];if(s[j-1]==')')sum2[j]++;}long long res=0;for(int i=1;i<=len;i++){if(s[i-1]=='('){res+=C(sum1[i]+sum2[i]-1,sum2[i]-1);if(res>MOD)res-=MOD;}}cout<<res<<endl;}
}