結果

問題 No.3043 括弧列の数え上げ
コンテスト
ユーザー srjywrdnprkt
提出日時 2025-03-04 10:47:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 1,385 bytes
コンパイル時間 2,740 ms
コンパイル使用メモリ 198,800 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2025-03-04 10:47:39
合計ジャッジ時間 5,054 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       dp(i,j)=i文字までで(-)=jであるものの総数
       dp(0,0)=1
       i文字目を(にするとき
       dp(i,j) += dp(i-1,j-1)
       i文字目を)にするとき
       dp(i,j) += dp(i-1, j+1)
       dp2(i,j) += (j * dp(i-1,j+1)) * dp(N-i, j) 
       深さjになるのがdp(i-1, j+1)個, 
       残りのN-i文字で対応が取れるようにするには,(-)がj個となるような括弧列を反転して繋げれば良い。
       よって、j * dp(i-1, j+1) * dp(N-i, j)を答えに足す。
    
    ()()() 0
    (())() 1
    ()(()) 1
    ((())) 2+1
    (()()) 1+1
    */

    int N;
    cin >> N;

    if (N % 2 == 1){
        cout << 0 << endl;
        return 0;
    }
    vector dp(N+1, vector<mint>(N/2+1));
    mint ans=0;

    dp[0][0] = 1;
    for (int i=1; i<=N; i++){
        for (int j=0; j<=N/2; j++){
            if (j) dp[i][j] += dp[i-1][j-1];
            if (j != N/2) dp[i][j] += dp[i-1][j+1];
        }
    }

    for (int i=1; i<=N; i++){
        for (int j=1; j<=N/2; j++){
            if (j != N/2) ans += dp[i-1][j+1] * j * dp[N-i][j];
        }
    }

    cout << ans.val() << endl;

    return 0;
}
0