记录编号	572235	评测结果	AWATTTTTTT
题目名称	[CF629C]Famil Door and Brackets	最终得分	20
用户昵称	➥Q小白小黑233	是否通过	未通过
代码语言	C++	运行时间	14.222 s
提交时间	2022-06-29 15:44:15	内存使用	12.67 MiB

#include<cstdio>
#include<cmath>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<utility>
#include<algorithm>
#include<string>

using namespace std;

stack <char> s,t;
int n,m;
int mod=int(10e9+7);
int lb=0,rb=0;
string may[200002]={};
string S; 
int cnt=0,re=0;
void dfs();
bool ok(string in);
void afind(string in,int r,int l);
void news(string in);
int main(){
	freopen("tribrackets.in","r",stdin);
	freopen("tribrackets.out","w",stdout);
	
	cin>>n>>m;
	cin>>S;
	
	int i;
	for(i=0;i<m;i++){
		s.push(S[i]);
		if(S[i]=='('){
			lb++;//(
		}
		else if(S[i]==')') {
			rb++;//)
		}
	}
//	cout<<ok(S)<<endl;
	if(n%2==1){
		cout<<0<<endl;
	}else if(lb>n/2||rb>n/2){
		cout<<0<<endl;
	}else{
		bool ok=true;
		while(ok&&!s.empty()){
			char t0p=s.top();
			if(t0p==')')
				t.push(t0p);
			else{
				if(!t.empty()){
					t.pop();
				}else{
					ok=false;
				}
			}
			s.pop();
		}
		if(ok){
			cout<<1<<endl;
		}else{
			news("");
//			dfs();
			cout<<re<<endl;
		}
	}
	
	return 0;
}
void afind(string in,int r,int l){
	if(in.length()>=n){
		may[++n]=in;
//		cout<<in<<endl;
		return;
	}
	if(r<=l&&l>0&&l<=n/2){
		afind(in+'(',l+1,r);
		afind(in+')',l,r+1);
	}else if(l==0){
		afind(in+'(',l+1,r);
	}else if(l==n/2){
		afind(in+')',l,r+1);
	}
	return ;
}
void news(string in){
	int ct=in.length();
	if(ct==n-m){
//		may[++cnt]=in; 
//		cout<<in<<endl;
		for(int j=0;j<n-m;j++){
			string ts=in;
			ts.insert(j,S);
			if(ok(ts)){
//				cout<<ts<<endl;
				re++;
			}
		}
		return;
	}
	news(in+'(');
	news(in+')');
//	cout<<"OK"<<endl;
} 
void dfs(){
	news("");
	for(int i=1;i<=cnt;i++){
		for(int j=0;j<n;j++){
			string ts=may[i];
			ts.insert(j,S);
			if(ok(ts)){
//				cout<<ts<<endl;
				re++;
			}
				
		}
	}
} 
bool ok(string in){
	stack <char> st; 
	
	bool o=true;
	for(int i=0;i<in.length();i++){
		if(in[i]=='(')
			st.push(in[i]);
		else{
			if(st.empty()||st.top()!='('){
				o=false;
			}else{
				st.pop();
			}
		}
	}
	if(!st.empty())
		o=false;
	return o;
}