結果

問題 No.3213 depth max K
コンテスト
ユーザー moon17
提出日時 2025-07-25 23:11:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,903 bytes
コンパイル時間 855 ms
コンパイル使用メモリ 90,864 KB
実行使用メモリ 15,944 KB
最終ジャッジ日時 2025-07-25 23:12:32
合計ジャッジ時間 6,966 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Original Python code:
// n,k=map(int,input().split())
// M=998244353
// dp=[[0]*3 for _ in range(n+1)]
// dp[0][0]=1
// for i in range(1,2*n+1):
//   ndp=[[0]*3 for _ in range(n+1)]
//   for j in range(n+1):
//     if j+1<=n:
//       if j+1==k:
//         ndp[j+1][1]+=sum(dp[j][:2])%M
//       elif j+1>k:
//         ndp[j+1][2]+=sum(dp[j])%M
//       else:
//         ndp[j+1][0]+=dp[j][0]%M
//         ndp[j+1][1]+=dp[j][1]%M
//         ndp[j+1][2]+=dp[j][2]%M
//     if j-1>=0:
//       ndp[j-1][0]+=dp[j][0]%M
//       ndp[j-1][1]+=dp[j][1]%M
//       ndp[j-1][2]+=dp[j][2]%M
//   dp=ndp
// print(dp[0][1]%M)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    const int M = 998244353;
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= 2 * n; ++i) {
        vector<vector<int>> ndp(n + 1, vector<int>(3, 0));
        for (int j = 0; j <= n; ++j) {
            if (j + 1 <= n) {
                if (j + 1 == k) {
                    int s = (dp[j][0] + dp[j][1]) % M;
                    ndp[j + 1][1] = (ndp[j + 1][1] + s) % M;
                } else if (j + 1 > k) {
                    int s = ((dp[j][0] + dp[j][1]) % M + dp[j][2]) % M;
                    ndp[j + 1][2] = (ndp[j + 1][2] + s) % M;
                } else {
                    ndp[j + 1][0] = (ndp[j + 1][0] + dp[j][0]) % M;
                    ndp[j + 1][1] = (ndp[j + 1][1] + dp[j][1]) % M;
                    ndp[j + 1][2] = (ndp[j + 1][2] + dp[j][2]) % M;
                }
            }
            if (j - 1 >= 0) {
                ndp[j - 1][0] = (ndp[j - 1][0] + dp[j][0]) % M;
                ndp[j - 1][1] = (ndp[j - 1][1] + dp[j][1]) % M;
                ndp[j - 1][2] = (ndp[j - 1][2] + dp[j][2]) % M;
            }
        }
        dp = move(ndp);
    }
    cout << dp[0][1] % M << endl;
    return 0;
}
0