Codeforces 785 D. Anton and School - 2
2024-10-19 01:29:05
题目链接:http://codeforces.com/contest/785/problem/D
我们可以枚举分界点,易知分界点左边和右边分别有多少个左括号和右括号,为了不计算重复我们强制要求选择分界点左边的那一个左括号(也就是说如果枚举的这个分界点的左边这个位置没有左括号就强制这个位置不产生贡献)。
对于一个分界点我们记它左边有$le[x]$个左括号,右边有$ri[x]$个右括号。
${Ans=\sum_{x=1}^{n-1} \sum _{i=1}^{min(le[x]-1,ri[x]])}C(le[x]-1,i)*C(r[x],i)}$
${=\sum_{x=1}^{n-1} C(le[x]-1+ri[x],ri[x])}$
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 1000010
#define llg long long
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
#define md 1000000007
llg n,m,le[maxn],ri[maxn],inv[maxn],fac[maxn]; char c[maxn]; llg ksm(llg a,llg b)
{
llg ans=;
while (b)
{
if (b&) ans*=a,ans%=md;
a*=a,a%=md;
b/=;
}
return ans;
} llg C(llg N,llg M)
{
if (M==) return ;
return fac[N]*inv[M]%md*inv[N-M]%md;
} int main()
{
yyj("D");
scanf("%s",c+);
n=strlen(c+);
llg p=;
for (llg i=;i<=n;i++)
{
if (c[i]=='(') p++;
le[i+]=p;
}
p=;
for (llg i=n;i>=;i--)
{
if (c[i]==')') p++;
ri[i]=p;
}
fac[]=;
llg ans=;
for (llg i=;i<=n*+;i++)
fac[i]=fac[i-]*i%md,inv[i]=ksm(fac[i],md-);
// fac[0]=0;
for (llg i=;i<=n;i++)
if (le[i] && ri[i] && c[i-]=='(')
ans+=C(le[i]+ri[i]-,ri[i]-),ans%=md;
cout<<ans;
return ;
}
最新文章
- [deviceone开发]-一个固定列,可以上下左右滑动的表格示例
- 浅谈Excel开发:三 Excel 对象模型
- Web 前端开发精华文章集锦(jQuery、HTML5、CSS3)【系列十九】
- 和我一起学python,控制语句 (life is short ,we need python)
- 跟我一起学WCF(4)——第一个WCF程序
- tomcat java.net.BindException: Cannot assign requested address 解决方法
- IOS之Foundation之探究学习Swift实用基础整理<;一>;
- C#对 Dictionary进行排序 转
- Android打造带透明圆弧的ImageView
- cat主要有三大功能
- ASP.NET Web API的核心对象:HttpController
- ACE 容器之三 ACE_Unbounded_Queue的使用
- About struct in C
- [SCOI 2010]字符串
- 面向对象(OOP)基本概念
- UOJ#104. 【APIO2014】Split the sequence 动态规划 斜率优化
- SSM 记录
- Page结构
- GUI程序设计2
- php 添加数据库的几种方法