Codeforces785D. Anton and School - 2(组合数学）_综合

题意：

问你一共有多少个子串，满足下列条件：

①长度为偶数

②前一半是（
③后一半是）

④子串不必要连续。

解题思路：

首先需要知道一个公式

解题思路：
* O( n )的预处理。很显然需要统计一下每个位置前面的（有多少个，后面的）有多少个，才可以方便计数。
* 算出对每一个位置前后的（）有多少种匹配，为了保证不重复，所以我们要求一定要使用当前位置的（，设当前位置前面有n个（包括本身，后面有m个）。所以对于每一个（出现的位置，可能有的总的组合数为

∑ni=1(Ci?1n?1?Cim) 如果 n>m ，对应位置组合数为0，结论不变。
*

∑ni=1(Ci?1n?1?Cim) =

∑ni=1(Cn?in?1?Cim) =

Cnn+m?1 (最后一步由范德蒙恒等式证) 并且由最后的结果可以看出

PS:注意inv[i]为i的阶乘的逆元

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int N = 200005;
ll inv[N], fact[N];
int l[N], r[N];
char s[N];
ll C(int n, int m)
{return fact[n+m-1]*inv[n]%MOD*inv[m-1]%MOD;
}
int power_mod(int a, int index)
{int ret = 1;while (index){if (index & 1){ret = 1ll * ret * a % MOD;}a = 1ll * a * a % MOD;index >>= 1;}return ret;
}
void init()
{fact[0] = 1;for(int i = 1; i < N; i++)fact[i] = fact[i-1] * i % MOD;inv[N - 1] = power_mod(fact[N - 1], MOD - 2);for (int i = N - 2; i >= 0; -- i){inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;}
}
int main()
{init();while(scanf("%s", s+1) != EOF){int len = strlen(s+1);l[0] = r[len+1] = 0;for(int i = 1; i <= len; i++)l[i] = l[i-1] + (s[i] == '(');for(int i = len; i >= 1; i--)r[i] = r[i+1] + (s[i] == ')');ll ans = 0;for(int i = 1; i <= len; i++){if(s[i] != '(') continue;ans = (ans + C(l[i], r[i])) % MOD;}printf("%I64d\n", ans);}return 0;
}