結果

問題 No.3099 Parentheses Decomposition
コンテスト
ユーザー ha_chan
提出日時 2025-05-23 17:28:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 964 bytes
コンパイル時間 1,981 ms
コンパイル使用メモリ 197,156 KB
実行使用メモリ 12,104 KB
最終ジャッジ日時 2025-05-23 17:28:17
合計ジャッジ時間 3,946 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:27:29: warning: iteration 999999 invokes undefined behavior [-Waggressive-loop-optimizations]
   27 |         fac[i+1]=fac[i]*(i+1);
      |                             ^
main.cpp:3:37: note: within this loop
    3 | #define rep(i, n) for (int i = 0; i < (int)(n); i++)
      |                                     ^
main.cpp:26:5: note: in expansion of macro ‘rep’
   26 |     rep(i,1000000){
      |     ^~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<VL> VVL;
typedef long long LL;
#define all(a) (a).begin(), (a).end()
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back

#include <atcoder/modint>
using mint = atcoder::modint998244353;

mint fac[1000000];
mint inv[1000000];

mint f(int n,int a){
    return fac[n]/(fac[a]*fac[n-a]);
}   

int main() {
    fac[0]=1;
    rep(i,1000000){
        fac[i+1]=fac[i]*(i+1);
    }
    inv[1000000-1]=fac[1000000-1].inv();
    for(int i=1000000-2;i>=0;i--){
        inv[i]=inv[i+1]*(i+1);
    }
    int n;string s;cin>>n>>s;
    int m=n/2;
    mint ans=0;
    if(s[1]==')'){ans=mint(2).pow(m);}
    else{
        rep(a,m+1){
            mint s=f(m,a);
            ans+=s*s;
        }
    }
    cout<<ans.val()<<endl;
}
0