結果
問題 | No.3043 括弧列の数え上げ |
ユーザー |
|
提出日時 | 2025-02-28 22:33:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,026 bytes |
コンパイル時間 | 1,978 ms |
コンパイル使用メモリ | 197,476 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-28 22:33:56 |
合計ジャッジ時間 | 3,318 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} #include<atcoder/modint> using mint=atcoder::modint998244353; void Solve(){ int N; cin>>N; vector<mint>cnt(N+1),dp(N+1); cnt[0]=1; for(int i=0;i<N;i++){ vector<mint>nxt_cnt(N+1); vector<mint>nxt_dp(N+1); for(int j=0;j<=N;j++){ if(j+1<=N){ nxt_cnt[j+1]+=cnt[j]; nxt_dp[j+1]+=dp[j]; } if(j-1>=0){ nxt_cnt[j-1]+=cnt[j]; nxt_dp[j-1]+=dp[j]+(j-1)*cnt[j]; } } swap(cnt,nxt_cnt); swap(dp,nxt_dp); } mint ans=dp[0]; cout<<ans.val()<<"\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); Solve(); }