結果

問題 No.3099 Parentheses Decomposition
ユーザー Tourmaline
提出日時 2025-04-11 21:25:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 4,952 bytes
コンパイル時間 5,322 ms
コンパイル使用メモリ 333,056 KB
実行使用メモリ 9,780 KB
最終ジャッジ日時 2025-04-11 21:25:42
合計ジャッジ時間 6,552 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll=long long;
using LL=__int128;
using ld=long double;
using uint=unsigned int;
using ull=unsigned long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<typename T> using vc=vector<T>;
template<typename T> using vvc=vector<vc<T>>;
template<typename T> using vvvc=vector<vvc<T>>;
using vi=vc<int>;
using vvi=vvc<int>;
using vd=vc<ld>;
using vvd=vvc<ld>;
using vl=vc<ll>;
using vvl=vvc<ll>;
using vs=vc<string>;
using vp=vc<pll>;
using vvp=vvc<pll>;

#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll _=0;_<ll(n);_++)
#define rep2(i,n) for(ll i=0;i<ll(n);i++)
#define rep3(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define rep(...) overload3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(ll _=ll(n);_--;)
#define rrep2(i,n) for(ll i=ll(n);i--;)
#define rrep3(i,a,b) for(ll i=ll(b);i-->ll(a);)
#define rrep(...) overload3(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)

#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()

template<int m>
ostream& operator<<(ostream& os,static_modint<m> v){
	os<<v.val();
	return os;
}
istream& operator>>(istream& is,__int128& v){
    string s;
    is>>s;
    v=0;
	rep(i,s.size())if(isdigit(s[i])) v=v*10+s[i]-'0';
	if(s[0]=='-') v*=-1;
    return is;
}
ostream& operator<<(ostream& os,__int128 v){
	ostream::sentry s(os);
	if(s){
		__uint128_t t=v<0?-v:v;
		char buf[128];
		char* d=end(buf);
		do{
			d--;
			*d="0123456789"[t%10];
			t/=10;
		}while(t);
		if(v<0){
			d--;
			*d='-';
		}
		int len=end(buf)-d;
		if(os.rdbuf()->sputn(d,len)!=len) os.setstate(ios_base::badbit);
	}
	return os;
}
template<typename S,typename T>
ostream& operator<<(ostream& os,pair<S,T> a){
	os<<a.first<<' '<<a.second;
	return os;
}
template<typename T>
ostream& operator<<(ostream& os,vector<T> a){
	if(a.empty()) return os;
	os<<a[0];
	rep(i,1,a.size()) os<<' '<<a[i];
	return os;
}
template<typename T>
ostream& operator<<(ostream& os,vector<vector<T>> a){
	if(a.empty()) return os;
	os<<a[0];
	rep(i,1,a.size()) os<<endl<<a[i];
	return os;
}
void output(auto x){cout<<x<<endl;}
template<typename T>
void output(vector<T> a,bool next_line=0){
	if(next_line){
		for(auto x:a) output(x);
	}
	else cout<<a<<endl;
}

void debug(auto ...vs){
	((cout<<vs<<", "),...)<<endl;
}

void syosu(int x=15){cout<<fixed<<setprecision(x);}
void YN(bool x){cout<<(x?"Yes":"No")<<endl;}
void chmin(auto &x,auto y){if(x>y) x=y;}
void chmax(auto &x,auto y){if(x<y) x=y;}

template<typename T>
void read(vector<T> &a,int n,int off=0){
	a=vector<T>(n);
	for(auto &i:a){
		cin>>i;
		i-=off;
	}
}

void read(vs &a,int n){
	a=vs(n);
	for(auto &i:a) cin>>i;
}

template<typename T>
void read(vector<pair<T,T>> &a,int n,int off=0){
	a=vector<pair<T,T>>(n);
	for(auto &[x,y]:a){
		cin>>x>>y;
		x-=off,y-=off;
	}
}

template<typename T>
void read(vector<vector<T>> &a,int n,int m,int off=0){
	a=vector<vector<T>>(n,vector<T>(m));
	for(auto &i:a) for(auto &j:i){
		cin>>j;
		j-=off;
	}
}

template<typename T>
void readGraph(vector<vector<T>> &g,int n,int m,bool rv=1,int off=1){
	g=vector<vector<T>>(n);
	for(int i=0;i<m;i++){
		T u,v;
		cin>>u>>v;
		u-=off,v-=off;
		g[u].emplace_back(v);
		if(rv) g[v].emplace_back(u);
	}
}

template<typename T>
void readGraph(vector<vector<pair<T,T>>> &g,int n,int m,bool id=0,bool rv=1,int off=1){
	g=vector<vector<pair<T,T>>>(n);
	for(int i=0;i<m;i++){
		if(id){
			T u,v;
			cin>>u>>v;
			u-=off,v-=off;
			g[u].emplace_back(v,i);
			if(rv) g[v].emplace_back(u,i);
		}
		else{
			T u,v,w;
			cin>>u>>v>>w;
			u-=off,v-=off;
			g[u].emplace_back(v,w);
			if(rv) g[v].emplace_back(u,w);
		}
	}
}

string toBinary(ll x,ll n,bool rev=0){
	assert(0<=x&&x<1LL<<n);
	string s(n,'0');
	for(int i=0;i<n;i++) if(x&1LL<<i) s[n-i-1]='1';
	if(rev) reverse(s.begin(),s.end());
	return s;
}

constexpr ll inf=1<<30;
constexpr ll INF=1ll<<60;
const ld pi=acosl(-1);
constexpr ld eps=1e-9;
//constexpr ll mod=1e9+7;
constexpr ll mod=998244353;
constexpr int dx[9]={-1,0,1,0,1,1,-1,-1,0};
constexpr int dy[9]={0,1,0,-1,1,-1,1,-1,0};

using mint=static_modint<mod>;
using vm=vc<mint>;
using vvm=vvc<mint>;

void main2();

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll q=1;
//	cin>>q;
	while(q--) main2();
}

const int MX=500005;
mint F[MX+1],ivF[MX+1],iv[MX+1];

void Init(){
	F[0]=1;
	for(int i=1;i<=MX;i++) F[i]=F[i-1]*i;
	ivF[MX]=F[MX].inv();
	for(int i=MX-1;i>=0;i--) ivF[i]=ivF[i+1]*(i+1);
	for(int i=1;i<MX;i++) iv[i]=ivF[i]*F[i-1];
}

mint nCk(ll n,ll k){
	assert(0<=k&&k<=n);
	if(n<=MX) return F[n]*ivF[n-k]*ivF[k];
	if(n-k<k) return nCk(n,n-k);
	mint r=ivF[k];
	for(int i=0;i<k;i++) r*=n-i;
	return r;
}

void main2(){
	Init();
	ll n;
	string s;
	cin>>n>>s;
	mint rs=0;
	n>>=1;
	if(s[1]=='('){
		rep(i,n+1) rs+=nCk(n,i)*nCk(n,i);
	}
	else{
		rs=mint(2).pow(n);
	}
	output(rs);
}
0