题目链接
problem
给出一个括号序列,要求删除一些括号使得剩下的括号序列是个匹配的括号序列,且改括号序列左边全部为左括号,右边全部为右括号。
solution
考虑枚举左右括号交界的位置(x),为了避免重复计算,强制要求(x)左边的第一个左括号必选。然后枚举(x)的时候只枚举左括号的位置。
然后枚举括号序列的长度。假设长度为(2i),那么左右括号就分别有(i)个,假设左边有(n)个左括号,右边有(m)个右括号。那么该位置的答案就是(sumlimits_{i=1}^{min(n,m)}c_{n-1}^{i-1}c_{m}^i)
观察上面这个式子,当(i=0)时没有贡献,所以我们可以等价的写成(sumlimits_{i=0}^{min(n,m)}c_{n-1}^{i-1}c_m^i)
假设(nle m)
上面的式子也可以写成
(sumlimits_{i=0}^nc_{n-1}^{n-i}c_m^i)
考虑这个东西的组合意义,也就相当于有(n+m-1)个物品从中选(n)个。
所以上面的东西其实就是(c_{n+m-1}^n)然后就可以(o(1))求了。
可以发现,当(mle 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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/601204.html