結果

問題 No.3099 Parentheses Decomposition
コンテスト
ユーザー Today03
提出日時 2025-04-11 22:06:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 3,843 bytes
コンパイル時間 3,099 ms
コンパイル使用メモリ 279,140 KB
実行使用メモリ 11,592 KB
最終ジャッジ日時 2025-04-11 22:06:22
合計ジャッジ時間 4,169 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define IO ios::sync_with_stdio(false),cin.tie(nullptr);
#define LB(v,x) (int)(lower_bound(ALL(v),x)-(v).begin())
#define UQ(v) sort(ALL(v)), erase(unique(ALL(v)),v.end())

template<typename T> bool chmax(T&a, const T&b){ if(a<b){ a=b; return true; } return false; }
template<typename T> bool chmin(T&a, const T&b){ if(b<a){ a=b; return true; } return false; }
template<typename T> using rpriority_queue=priority_queue<T,vector<T>,greater<T>>;
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>; using VS=vector<string>;
using PL=pair<ll,ll>; using VP=vector<PL>; using TL=tuple<ll,ll,ll>; using WG=vector<vector<pair<int,ll>>>;



/// @file modint.hpp
/// @brief ModInt
template<ll MOD>
struct ModInt{
	ModInt(ll x=0){value=(x>=0?x%MOD:MOD-(-x)%MOD);}
	ModInt operator-()const{return ModInt(-value);}
	ModInt operator+()const{return ModInt(*this);}
	ModInt&operator+=(const ModInt&other){
		value+=other.value;
		if(value>=MOD)value-=MOD;
		return*this;
	}
	ModInt&operator-=(const ModInt&other){
		value+=MOD-other.value;
		if(value>=MOD)value-=MOD;
		return*this;
	}
	ModInt&operator*=(const ModInt other){
		value=value*other.value%MOD;
		return*this;
	}
	ModInt&operator/=(ModInt other){
		(*this)*=other.inv();
		return*this;
	}
	ModInt operator+(const ModInt&other)const{return ModInt(*this)+=other;}
	ModInt operator-(const ModInt&other)const{return ModInt(*this)-=other;}
	ModInt operator*(const ModInt&other)const{return ModInt(*this)*=other;}
	ModInt operator/(const ModInt&other)const{return ModInt(*this)/=other;}
	ModInt pow(ll x)const{
		ModInt ret(1),mul(value);
		while(x){
			if(x&1)ret*=mul;
			mul*=mul;
			x>>=1;
		}
		return ret;
	}
	ModInt inv()const{return pow(MOD-2);}
	bool operator==(const ModInt&other)const{return value==other.value;}
	bool operator!=(const ModInt&other)const{return value!=other.value;}
	friend ostream&operator<<(ostream&os,const ModInt&x){return os<<x.value;}
	friend istream&operator>>(istream&is,ModInt&x){
		ll v;
		is>>v;
		x=ModInt<MOD>(v);
		return is;
	}
	ll val(){return value;}
	static constexpr ll get_mod(){return MOD;}

private:
	ll value;
};
using Mod998=ModInt<998244353>;
using Mod107=ModInt<1000000007>;


/// @file comb.hpp
/// @brief 二項係数・階乗計算
template<typename T>
struct Combinatorics{
	Combinatorics()=default;

	/// @brief 二項係数の前計算
	/// @note O(N)
	Combinatorics(int n){
		fac=vector<T>(n+1);
		finv=vector<T>(n+1);
		fac[0]=1;
		for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i;
		finv[n]=fac[n].inv();
		for(int i=n;i>=1;i--)finv[i-1]=finv[i]*i;
	}

	/// @brief nCr を返す
	/// @note n < 0, r < 0, n < r のときは 0 を返す
	T comb(ll n,ll r){
		if(n<0||r<0||n-r<0)return 0;
		return fac[n]*finv[r]*finv[n-r];
	}

	/// @brief nPr を返す
	/// @note n < 0, r < 0, n < r のときは 0 を返す
	T perm(ll n,ll r){
		if(n<0||r<0||n-r<0)return 0;
		return fac[n]*finv[n-r];
	}

	/// @brief n! を返す
	T factrial(int n){return fac[n];}

	/// @brief (n!)^-1 を返す
	T factinv(int n){return finv[n];}

	/// @brief nCr を返す
	T operator()(ll n,ll r){return comb(n,r);}

private:
	vector<T>fac,finv;
};



using mint=Mod998;

bool valid(string S){
	int now=0;
	for(char c:S){
		if(c=='(') now++;
		else now--;
		if(now<0) return false;
	}
	return now==0;
}

ll naive(string S){
	int N=S.size();

	ll ans=0;
	REP(b,1<<N){
		string t,u;
		REP(i,N){
			if(b>>i&1) t.push_back(S[i]);
			else u.push_back(S[i]);
		}
		if(valid(t)&&valid(u))ans++;
	}

	return ans;
}


int main(){

	int N;string S;
	cin>>N>>S;

	Combinatorics<mint>com(N);

	if(S[1]=='(') cout<<com(N,N/2)<<endl;
	else cout<<mint(2).pow(N/2)<<endl;
}
0