F.小红的括号串

题解

Raney 引理： 对于 ，如果 ，则其所有循环位移中恰好有一个满足所有的前缀和都是正数。

将括号串中的左括号视为 -1，右括号视为 1，则合法括号串需要满足序列和为 0。

考虑在这个序列中加上一个 -1，再将所有数取反，此时序列满足 Raney 引理的应用条件。

并且因为恰好有一个循环位移合法，所以此时序列的第一位必定为 1（即我们取反前加的 -1）。把这个 1 去掉再取反即为合法括号串。

因此所有满足序列和为 0 的括号串均合法。记左括号数为 ，右括号数为 ，当 为偶数时答案为 。

Bonus：尝试解决 P6672 你的生命已如风中残烛。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define M 1000000007
#define N 200000

int i,j,k,n,m,t;
ll jc[N+50],inv[N+50];
string s;

ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
ll c(ll n,ll m){if(n<m||n<0||m<0){return 0;}return jc[n]*inv[m]%M*inv[n-m]%M;}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	jc[0]=inv[0]=1;
	for(i=1;i<=N;i++)jc[i]=jc[i-1]*i%M;
	inv[N]=ksm(jc[N],M-2);
	for(i=N-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%M;
	
	cin>>n>>s;
	if(n&1){
		cout<<0; return 0;
	}
	for(auto c:s){
		if(c=='(')i++;
		else if(c==')')j++;
	}
	cout<<c(n-i-j,n/2-i);
}