cf785D(组合数学)

题目链接: http://codeforces.com/problemset/problem/785/D

题意: 左边全为 '(' 右边全为 ')' 且两者数量想等的字符串称为 RSBS. 给出一个由 '(' 和 ')' 组成的字符串, 问其有多少子序列是 RSBS.

思路: 可以先预处理一下, 用 a[i] 记录 i 前面(包括 i 这个位置)的 '(' 的数目, b[i] 记录 i 后面(包括 i 这个位置)的 ')' 的数目, 然后从左往右枚举以 '(' 结尾的情况,

那么当前情况下的 RSBS 数目为:

C(a[i] - 1, 0) * C(b[i], 1) + C(a[i] - 1, 1) * C(b[i], 2) + C(a[i] - 1, 2) * C(b[i], 3) + ...

= ∑^{min(a-1, b-1)}₀C(a - 1, x) * C(b, x + 1)

= ∑^{min(a-1, b-1)}₀C(a - 1, a - 1 - x) * C(b, x + 1)

= C(a - 1 + b, a) (范德蒙恒等式)

然后将所有情况的 RSBS 数目累加一下就好啦.

注意这里的组合数比较大, 取模的话需要用到 exgcd 或者快速幂.

代码1: 快速幂求组合数取模 C(n, m) % mode = (n! % mode) * get_pow((n - m)! * m! % mode, mode - 2) % mode. (这个公式能通过费马小定理变换得到).

 1 #include <iostream>
 2 #define ll long long
 3 using namespace std;
 4 
 5 const int mode = 1e9 + 7;
 6 const int MAXN = 2e5 + 10;
 7 ll a[MAXN], b[MAXN], gel[MAXN];
 8 string s;
 9 
10 ll get_pow(ll x, int n){
11     ll ans = 1;
12     while(n){
13         if(n & 1) ans = ans * x % mode;
14         x = x * x % mode;
15         n >>= 1;
16     }
17     return ans;
18 }
19 
20 int main(void){
21     ll ans = 0;
22     cin >> s;
23     if(s[0] == '(') a[0] = 1;
24     for(int i = 1; i < s.size(); i++){
25         if(s[i] == '(') a[i] = a[i - 1] + 1;
26         else a[i] = a[i - 1];
27     }
28     for(int i = s.size() - 1; i >= 0; i--){
29         if(s[i] == ')') b[i] = b[i + 1] + 1;
30         else b[i] = b[i + 1];
31     }
32     gel[0] = 1;
33     for(int i = 1; i < MAXN; i++){
34         gel[i] = gel[i - 1] * i % mode;
35     }
36     for(int i = 0; i < s.size(); i++){
37         if(s[i] == ')') continue;
38         ll cnt1 = a[i], cnt2 = a[i] + b[i] - 1;
39         ans = (ans + (gel[cnt2] * get_pow(gel[cnt1] * gel[cnt2 - cnt1] % mode, mode - 2)) % mode) % mode;
40     }
41     cout << ans << endl;
42     return 0;
43 }

View Code

代码2: 用乘法逆元求得组合数取模

 1 #include <iostream>
 2 #define ll long long
 3 using namespace std;
 4 
 5 const int mode = 1e9 + 7;
 6 const int MAXN = 2e5 + 10;
 7 ll a[MAXN], b[MAXN], gel[MAXN];
 8 string s;
 9 
10 void exgcd(ll a, ll b, ll &x, ll &y){
11     if(!b){
12         y = 0;
13         x = 1;
14         return;
15     }
16     exgcd(b, a % b, y, x);
17     y -= a / b * x;
18 }
19 
20 int main(void){
21     ll ans = 0;
22     cin >> s;
23     if(s[0] == '(') a[0] = 1;
24     for(int i = 1; i < s.size(); i++){
25         if(s[i] == '(') a[i] = a[i - 1] + 1;
26         else a[i] = a[i - 1];
27     }
28     for(int i = s.size() - 1; i >= 0; i--){
29         if(s[i] == ')') b[i] = b[i + 1] + 1;
30         else b[i] = b[i + 1];
31     }
32     gel[0] = 1;
33     for(int i = 1; i < MAXN; i++){
34         gel[i] = gel[i - 1] * i % mode;
35     }
36     for(int i = 0; i < s.size(); i++){
37         if(s[i] == ')') continue;
38         ll cnt1 = a[i], cnt2 = a[i] + b[i] - 1;
39         ll cc1 = gel[cnt2], cc2 = gel[cnt2 - cnt1] * gel[cnt1] % mode;
40         ll x, y;
41         exgcd(cc2, mode, x, y);
42         x = (x % mode + mode) % mode;
43         ans = (ans + (cc1 * x) % mode) % mode;
44 
45     }
46     cout << ans << endl;
47     return 0;
48 }

View Code