Codeforces-785-D(范德蒙恒等式)
Codeforces-785-D(范德蒙恒等式)
Codeforces 785D-Anton and School - 2
题目原址
[http://codeforces.com/contest/785/problem/D]
题意
给一组只含 ’ ( ’ 和 ’ ) ’ 的字符串,你可以删去其中一些位置的括号,也可以不删,使得剩下的括号成为满足下列条件的括号组。
- "()"是一个好的括号组。
- 如果X是一个好的括号组,那么"(X)"也是一个好的括号组。
- 同时满足 1. 和 2. 的括号组是好的括号组。
删除不同位置括号得到好括号组算作是不同的方法,问有多少种方法能让原来的字符串变成好的括号组。
题解
想要得到好的括号组,对于字符串中的每个 ’ ( ’ ,就必定要从左边选取 k 个 ’ ( ’ ,再从右边选取 k+1 个 ’ ) ’ 。
所以对于每个位置,如果用 l 表示该括号左边的 ’ ( ’ 数, r 表示该括号右边的 ’ ) ’ 数,那么该位置能够组成好括号组的方法数为:
∑i=0min(l,r−1)Cli⋅Cri+1\sum_{i=0}^{min(l,r-1)}C_{l}^{i}\cdot{C_{r}^{i+1}}i=0∑min(l,r−1)Cli⋅Cri+1这样写会超时,用范德蒙不等式化简,其表达式为:
∑i=0kCni⋅Cmk−i=Cn+mk\sum_{i=0}^{k}C_{n}^{i}\cdot{C_{m}^{k-i}}=C_{n+m}^{k}i=0∑kCni⋅Cmk−i=Cn+mk证明从略,其实从选取的角度去看,公式本身就很有道理。化简方法为:
∑i=0min(l,r−1)Cli⋅Cri+1=∑i=0r−1Cli⋅Crr−1−i=Cl+rr−1\sum_{i=0}^{min(l,r-1)}C_{l}^{i}\cdot{C_{r}^{i+1}}=\sum_{i=0}^{r-1}C_{l}^{i}\cdot{C_{r}^{r-1-i}}=C_{l+r}^{r-1}i=0∑min(l,r−1)Cli⋅Cri+1=i=0∑r−1Cli⋅Crr−1−i=Cl+rr−1
先用两个数组预处理字符串,第一个数组表示某个位置(算上自己)左边总共有多少个 ’ ( ',第二个数组表示某个位置(算上自己)右边总共有多少个 ‘ ) ’ ,再对字符串从左到右遍历一遍,利用上述不等式累加求和即可。
组合数可以通过阶乘和逆元算出来。
对于阶乘的逆元,很显然,如果:
n!∗inv(n!)≡1(modm)n!*inv(n!)\equiv1(mod~m)n!∗inv(n!)≡1(mod m)那么 (n−1)!(n-1)!(n−1)! 的逆元:
(n−1)!∗(n∗inv(n!))≡1(modm)(n-1)!*(n*inv(n!))\equiv1(mod~m)(n−1)!∗(n∗inv(n!))≡1(mod m)用欧几里德算法算出最大的阶乘的逆元即可。
实现
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = (int)2e5+5;
const int mod = (int)1e9+7;
char s[maxn];
int suml[maxn],sumr[maxn];
ll fac[maxn],inv[maxn];
int i,j,k;
int x,y;void finv(int a,int b,int&x,int&y){//欧几里德算法 if(b==0){ x=1;y=0; return; } finv(b,a%b,y,x); y-=a/b*x%mod; return;
}
void ffac(){//初始化求0-maxn的阶乘和逆元inv[0]=fac[0]=1;for(i=1;i<maxn;i++)fac[i]=fac[i-1]*i%mod;finv(fac[maxn-1],mod,x,y);//欧几里德算逆元inv[maxn-1]=x;for(i=maxn-2;i>=0;i--)//其他阶乘逆元inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(int a,int b){//组合数if(b>a||b<0||a<0)return 0;elsereturn fac[a]*inv[b]%mod*inv[a-b]%mod;
}int main()
{scanf("%s",s);int len = strlen(s);//预处理 suml[0] = (s[0]=='(');for(i=1;i<len;i++)suml[i]=suml[i-1]+(s[i]=='(');sumr[len-1]=(s[len-1]==')');for(i=len-2;i>=0;i--)sumr[i]=sumr[i+1]+(s[i]==')');ffac();ll ans=0;for(i=0;i<len;i++)if(s[i]=='(')ans=(ans+C(suml[i]+sumr[i]-1,sumr[i]-1))%mod;//范德蒙恒等式printf("%I64d\n",ans);
}