結果
問題 | No.2528 pop_(backfront or not) |
ユーザー | Carpenters-Cat |
提出日時 | 2023-11-03 22:03:10 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 261 ms / 2,000 ms |
コード長 | 946 bytes |
コンパイル時間 | 1,753 ms |
コンパイル使用メモリ | 202,372 KB |
実行使用メモリ | 255,556 KB |
最終ジャッジ日時 | 2023-11-03 22:03:14 |
合計ジャッジ時間 | 3,949 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,672 KB |
testcase_01 | AC | 2 ms
5,680 KB |
testcase_02 | AC | 2 ms
5,688 KB |
testcase_03 | AC | 2 ms
5,704 KB |
testcase_04 | AC | 2 ms
7,792 KB |
testcase_05 | AC | 4 ms
18,060 KB |
testcase_06 | AC | 5 ms
22,168 KB |
testcase_07 | AC | 11 ms
36,536 KB |
testcase_08 | AC | 12 ms
42,696 KB |
testcase_09 | AC | 24 ms
75,544 KB |
testcase_10 | AC | 65 ms
130,968 KB |
testcase_11 | AC | 68 ms
135,076 KB |
testcase_12 | AC | 91 ms
161,764 KB |
testcase_13 | AC | 98 ms
169,976 KB |
testcase_14 | AC | 131 ms
185,852 KB |
testcase_15 | AC | 191 ms
231,580 KB |
testcase_16 | AC | 261 ms
255,424 KB |
testcase_17 | AC | 205 ms
255,492 KB |
testcase_18 | AC | 207 ms
255,556 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; ll const m = 998244353; int main () { int N; cin >> N; ll dp[4020][4020]; ll cb[4020][4020]; for (int n = 0; n <= N * 2 + 1; n ++) { cb[n][0] = cb[n][n] = 1; for (int r = 1; r < n; r ++) { cb[n][r] = (cb[n - 1][r] + cb[n - 1][r - 1]) % m; } } auto comb = [&](int n, int r) -> ll { if (r < 0 || n < r) return 0; return cb[n][r]; }; for (int l = 0; l <= N * 2; l ++) { for (int r = 0; r <= N * 2; r ++) { if (l + r == 0) { dp[l][r] = 1; } else if (l * r == 0) { dp[l][r] = 0; } else { dp[l][r] = (1ll + (l - 1) * (r - 1)) * dp[l - 1][r - 1]; dp[l][r] %= m; if (l > 2) { dp[l][r] += comb(l - 1, 2) * dp[l - 2][r]; dp[l][r] %= m; } if (r > 2) { dp[l][r] += comb(r - 1, 2) * dp[l][r - 2]; dp[l][r] %= m; } } } } for (int i = 0; i < N * 2 + 1; i ++) { cout << dp[i][N * 2 - i] << endl; } }