題目鏈接
problem
給出一個括號序列，要求洗掉一些括號使得剩下的括號序列是個匹配的括號序列，且改括號序列左邊全部為左括號，右邊全部為右括號，
solution
考慮列舉左右括號交界的位置\(x\)，為了避免重復計算，強制要求\(x\)左邊的第一個左括號必選，然后列舉\(x\)的時候只列舉左括號的位置，
然后列舉括號序列的長度，假設長度為\(2i\)，那么左右括號就分別有\(i\)個，假設左邊有\(n\)個左括號，右邊有\(m\)個右括號，那么該位置的答案就是\(\sum\limits_{i=1}^{min(n,m)}C_{n-1}^{i-1}C_{m}^i\)
觀察上面這個式子，當\(i=0\)時沒有貢獻，所以我們可以等價的寫成\(\sum\limits_{i=0}^{min(n,m)}C_{n-1}^{i-1}C_m^i\)
假設\(n\le m\)
上面的式子也可以寫成
\(\sum\limits_{i=0}^nC_{n-1}^{n-i}C_m^i\)
考慮這個東西的組合意義，也就相當于有\(n+m-1\)個物品從中選\(n\)個，
所以上面的東西其實就是\(C_{n+m-1}^n\)然后就可以\(O(1)\)求了，
可以發現，當\(m\le n\)時，推出的式子也是這個，
這樣總復雜度就成了\(O(n)\)
code
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<ctime>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int n;
const int N = 200100;
char s[N];
int cnta,cntb,jc[N],inv[N];
int C(int x,int y) {
return 1ll * jc[x] * inv[y] % mod * inv[x - y] % mod;
}
int qm(int x,int y) {
int ret = 1;
for(;y;y >>= 1,x = 1ll * x * x % mod) {
if(y & 1) ret = 1ll * ret * x % mod;
}
return ret;
}
int main() {
scanf("%s",s + 1);
n = strlen(s + 1);
jc[0] = 1;
for(int i = 1;i <= n;++i) jc[i] = 1ll * jc[i - 1] * i % mod;
for(int i = 0;i <= n;++i) inv[i] = qm(jc[i],mod - 2);
for(int i = 1;i <= n;++i) if(s[i] == ')') cntb++;
ll ans = 0;
for(int i = 1;i <= n;++i) {
if(s[i] == '(') {
cnta++;
ans += C(cnta + cntb - 1,cnta);
ans %= mod;
}
else cntb--;
}
cout<<ans;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/91716.html
標籤：C++
下一篇：記錄一次gdb debug經歷