結果
問題 |
No.3213 depth max K
|
ユーザー |
![]() |
提出日時 | 2025-07-25 23:09:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,666 ms / 2,000 ms |
コード長 | 1,710 bytes |
コンパイル時間 | 1,720 ms |
コンパイル使用メモリ | 200,672 KB |
実行使用メモリ | 394,752 KB |
最終ジャッジ日時 | 2025-07-25 23:10:11 |
合計ジャッジ時間 | 14,663 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
// Original Python code: // import sys // sys.setrecursionlimit(10**4) // MOD = 998244353 // N,K = list(map(int,input().split())) // // def f(n,now_depth,MAX_DEPTH): // if(n == 2*N):return 1 if now_depth == 0 else 0 // if(memo[n][now_depth] != -1):return memo[n][now_depth] // ret = 0 // # ( // if(now_depth < MAX_DEPTH):ret += f(n+1,now_depth+1,MAX_DEPTH) // # ) // if(now_depth >= 1):ret += f(n+1,now_depth-1,MAX_DEPTH) // // memo[n][now_depth] = ret % MOD // return ret % MOD // // memo = [[-1 for _ in range(K+1)] for _ in range(2*N)] // ans = f(0,0,K) // memo = [[-1 for _ in range(K+1)] for _ in range(2*N)] // ans -= f(0,0,K-1) // print(ans) #include <bits/stdc++.h> using namespace std; const int MOD = 998244353; int N, K; vector<vector<long long>> memo; // f(n, now_depth, MAX_DEPTH) long long f(int n, int now_depth, int MAX_DEPTH) { if (n == 2 * N) { return (now_depth == 0) ? 1 : 0; } if (memo[n][now_depth] != -1) { return memo[n][now_depth]; } long long ret = 0; // "(" if (now_depth < MAX_DEPTH) { ret += f(n + 1, now_depth + 1, MAX_DEPTH); } // ")" if (now_depth >= 1) { ret += f(n + 1, now_depth - 1, MAX_DEPTH); } return memo[n][now_depth] = (ret % MOD); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> K; // First count with MAX_DEPTH = K memo.assign(2 * N, vector<long long>(K + 1, -1)); long long ans = f(0, 0, K); // Reset memo and subtract count with MAX_DEPTH = K-1 memo.assign(2 * N, vector<long long>(K + 1, -1)); ans = (ans - f(0, 0, K - 1) + MOD) % MOD; cout << ans << "\n"; return 0; }