首页 > 代码库 > CodeForces 785D Anton and School - 2
CodeForces 785D Anton and School - 2
枚举，容斥原理，范德蒙恒等式。
先预处理每个位置之前有多少个左括号，记为$L[i]$。
每个位置之后有多少个右括号，记为$R[i]$。
然后枚举子序列中第一个右括号的位置，计算这个括号的第一个右括号的方案数。
即在它左边取$k$个左括号，在右边取$k-1$个右括号都是合法的方案，这个东西可以用范德蒙恒等式化成一个组合数以及容斥原理计算。
范德蒙恒等式：http://blog.csdn.net/acdreamers/article/details/31032763
#include <cstdio>#include <cmath>#include <cstring>#include <map>#include <algorithm>using namespace std;typedef long long LL; char s[200010];long long L[200010],R[200010];LL fac[200010];long long mod = 1e9+7;void init() { int i; fac[0] =1; for(i =1; i <= 200000; i++) fac[i] = fac[i-1]*i%mod; } LL pow(LL a, LL b) { LL tmp = a % mod, ans =1; while(b) { if(b &1) ans = ans * tmp % mod; tmp = tmp*tmp % mod; b >>=1; } return ans; } LL C(LL n, LL m) { if(m>n||m<0)return 0; return fac[n]*pow(fac[m]*fac[n-m],mod-2)%mod; } int main(){ init(); scanf("%s",s); int len = strlen(s); for(int i=1;i<=len;i++) { L[i] = L[i-1]; if(s[i-1]==‘(‘) L[i]++; } for(int i=len;i>=1;i--) { R[i] = R[i+1]; if(s[i-1]==‘)‘) R[i]++; } long long ans = 0; for(int i=1;i<=len;i++) { if(s[i-1]==‘(‘) continue; if(L[i]==0) continue; long long m,k1,k2; m = min(L[i],R[i]); if(m==0) k1=1; else k1 = C(L[i]+R[i],m); m = min(L[i],R[i]-1); if(m==0) k2=1; else k2 = C(L[i]+R[i]-1,m); long long k = (k1-k2+mod)%mod; ans = ( ans + k ) %mod; } printf("%lld\n",ans); return 0;}CodeForces 785D Anton and School - 2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。