結果
問題 | No.3099 Parentheses Decomposition |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }