[Codeforces] 785D. Anton and School - 2

題目連結:http://codeforces.com/problemset/problem/785/D

---

應該稍微簡單想兩下就會發現本題可以大致列出一個式子 $$ \sum_{\forall str[i]=(}{\sum_{j=1}^{\min(L_i, R_i)}{\binom{L_i-1}{j-1} \cdot \binom{R_i}{R_i-j}}} $$ 其中$L_i$代表前$i$個字元中左括號的個數，$R_i$則代表第$i$個字元後右括號的個數，這寫法的想法其實是我從左掃到右，然後計算第$i$個字元為最後一個佐括號時有幾種方法數，但是很明顯如果單單的照這樣做複雜度可能會到$O(n^2)$甚至應該會到$O(n^3)$，所以就需要用數學來把他優化，有個易證的組合恆等式 $$ \sum_{i=0}^{n}{\binom{n}{i} \cdot \binom{m}{i}} = \sum_{i=0}^{n}{\binom{n}{i} \cdot \binom{m}{m-i}} = \binom{n+m}{m} = \binom{n+m}{n}$$ (想像你要挑從$n+m$個東西裡挑$m$個，他不是出現在$n$個的那堆就是出現在$m$個的那堆)
於是乎我們就可以把一開始的式子稍微改寫幾下 $$ \sum_{\forall str[i]=(}{\sum_{j=1}^{\min(L_i, R_i)}{\binom{L_i-1}{j-1} \cdot \binom{R_i}{j}}} \\ = \sum_{\forall str[i]=(}{\sum_{j=1}^{\min(L_i, R_i)}{\binom{L_i-1}{j-1} \cdot \binom{R_i}{R_i-j}}} \\= \sum_{\forall str[i]=(}{ \binom{L_i+R_i-1}{R-1} } $$ 這樣就有了可能還是$O(n^2)$的做法，因為算組合需要$O(n)$，用二項式定理DP也還是$O(n^2)$，所以又要再觀察一點小事。發現你每次往右移動時$L$或$R$都頂多動一而已(即$L_i-L_{i-1}+R_i-R_{i-1} \leq 1 $)，所以算組合的時候也可以用一點基本的乘除運算來達到$O(1)$的轉移!!!，這樣我們就有了$O(n)/O(nlogn)$的做法了(算模逆元可以$O(n)$)。 $$ \binom{i+1}{j} = \binom{i}{j} \cdot (i+1) \div (i+1-j) \\ \binom{i-1}{j-1} = \binom{i}{j} \cdot j \div i $$

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MOD = 1e9 + 7;
const int N = 200000 + 5;

lld moni[N];
char str[N];
inline lld qPow(lld,int);
inline lld C(int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>str;
	int n = strlen(str);
	lld L=0, R=0;
	for(int i=0;i<n;i++) if(str[i]==')') R++;
	for(int i=1;i<=n;i++) moni[i]=qPow(i, MOD-2);
	lld ans = 0, pre=1;
	for(int i=0;i<n;i++){
		if(str[i]=='('){
			L++;
			pre = (((pre * (L+R-1)) % MOD) * moni[L]) % MOD;
			ans = (ans + pre)%MOD;
		}else if(str[i]==')'){
			R--;
			pre = (((pre * R) % MOD) * moni[L+R])%MOD;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

inline lld qPow(lld a, int x){
	lld r=1;
	while(x){
		if(x&1) r = (r*a)%MOD;
		x>>=1;
		a = (a*a)%MOD;
	}
	return r;
}