結果
問題 |
No.3043 括弧列の数え上げ
|
ユーザー |
|
提出日時 | 2025-02-28 22:55:56 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 874 bytes |
コンパイル時間 | 5,855 ms |
コンパイル使用メモリ | 332,756 KB |
実行使用メモリ | 34,688 KB |
最終ジャッジ日時 | 2025-02-28 22:56:05 |
合計ジャッジ時間 | 8,454 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using mint=modint998244353; int main() { int n; cin>>n; vector<vector<pair<mint,mint>>> dp(n+1,vector<pair<mint,mint>>(n+1)); dp[0][0]=make_pair(0,1); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(j>0){ dp[i+1][j-1].first+=dp[i][j].first+(j-1)*dp[i][j].second; dp[i+1][j-1].second+=dp[i][j].second; } dp[i+1][j+1].first+=dp[i][j].first; dp[i+1][j+1].second+=dp[i][j].second; } } //for(int i=1;i<n;i++)for(int j=0;j<=n;j++)cout<<dp[i][j].first.val()<<(j==n?"\n":" "); //cout<<endl; //for(int i=1;i<n;i++)for(int j=0;j<=n;j++)cout<<dp[i][j].second.val()<<(j==n?"\n":" "); cout<<(dp[n][0].first).val()<<endl; return 0; }