题目链接
hdu5184
题目概述
给出
对括号和前面一部分的括号序列,计算剩下的括号可以组成匹配的括号的数量,数据规模
,以EOF
作为程序的结束,结果可能会很大,所以需要对
取模.
解题思路
首先考虑合法有效的情况,将(
看做+1
,将)
看做-1
,此时前面是一个由部分(
组成的序列,现在剩下
个(
和
个)
,如何排列()
使得最后的这
个(
和)
组成的序列的之和等于0
.具体的解法的推导可以参考组合数学
这本书在推导那个定理是的证明.这里给出一个形象化的解释,任然使用那个格子模型,现在是从
点出发到达
点,要求不能越过对角线但是可以接触,将点
通过坐标变换的方式变到原点
,然后终点就变为了
,问题就转化为
数的计算模型了结果就是
.
注意
最初我用的是
定理来计算组合数取模,
,然而忽略了
的值非常大,一般
的值在
可以使用,对于这道题,用
定理模数是
,结果自然是TLE
.然后尝试把通过直接计算阶乘取模,通过逆元计算除数取模.因为这里的模数是一个素数,根据费马小定理:
可以用一个快速幂取模进行计算.前面的
,分子分母分别计算阶乘的值时可以取模,然后计算整个分式取模转化为分子乘以分母的逆取模,分母的逆用费马小定理和快速幂进行计算.
这道题的其它坑点集中在要处理非法的情况,也就是给出的括号数量和前面的序列,没法构成有效匹配的括号对,比如
为奇数时,左右括号数量不相等,一定不匹配;给出的前面的括号序列可能不匹配,或者没有给出的左右括号的数量一个超过
,一个不足等,都要考虑,不然会一直WA
.
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N = 1e6 + 5;
const int M = 1e9 + 7;// 快速幂取模
ll fast_exp_mod(ll a, ll b, ll p){ll ans = 1;while( b > 0){if( b & 1){ans = (ans * a) % p;}b >>= 1;a = (a * a) % p;}return ans;
}ll F[N] = {0};void calculate(){F[0] = 1;for (int i = 1; i < N; i++){F[i] = ((F[i - 1] % M) * (i % M)) % M;}
}// 基于递推式计算C(n,m)%p,(p为素数)
ll C(ll n, ll m, ll p){ll ans = 1;for (ll i = 1; i < m + 1; ++i){ll a = n - i + 1;ll b = i;ll temp = (a * fast_exp_mod(b, p - 2, p)) % p;ans = (ans * temp) % p;// T[i] = ans;}return ans;
}// Lucas定理
ll Lucas(ll n, ll m, ll p){if( m == 0){return 1;}return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}int main(int argc, const char** argv) {calculate();int n;char buf[N];while( ~scanf("%d%s", &n, buf) ) {int a = 0, b = 0;bool flag = true;for (int i = 0; buf[i] != '\0'; i++) {if( buf[i] =='(')++a;else if( buf[i] ==')'){++b;if( b > a){printf("0\n");flag = false;break;}}}if( flag ){if( n & 1 || b > a || n-b-(a-b) < 0){printf("%lld\n", 0ll);}else{ll ans = 0;a = n / 2 - a;b = n / 2 - b;if( a < 0 || b < 0){printf("%lld\n", 0ll);continue;}// ll ans = (Lucas(a + b, a, M) - Lucas(a + b, a - 1, M) + M)% M;ans = (((F[a + b] * (b + 1 - a)) % M) * fast_exp_mod((F[a] * F[b + 1]) % M, M - 2, M)) % M;printf("%lld\n", ans);}}}return 0;
}