結果

問題 No.2528 pop_(backfront or not)
ユーザー coindarwcoindarw
提出日時 2023-11-04 13:22:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 150 ms / 2,000 ms
コード長 2,734 bytes
コンパイル時間 4,929 ms
コンパイル使用メモリ 269,876 KB
実行使用メモリ 34,708 KB
最終ジャッジ日時 2023-11-04 13:22:59
合計ジャッジ時間 6,376 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 3 ms
4,348 KB
testcase_06 AC 3 ms
4,348 KB
testcase_07 AC 4 ms
4,348 KB
testcase_08 AC 6 ms
4,424 KB
testcase_09 AC 15 ms
6,080 KB
testcase_10 AC 40 ms
10,948 KB
testcase_11 AC 43 ms
11,740 KB
testcase_12 AC 60 ms
15,436 KB
testcase_13 AC 66 ms
16,824 KB
testcase_14 AC 81 ms
19,660 KB
testcase_15 AC 123 ms
28,900 KB
testcase_16 AC 150 ms
34,708 KB
testcase_17 AC 150 ms
34,708 KB
testcase_18 AC 149 ms
34,708 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef ONLINE_JUDGE
#include <bits/stdc++.h>

#include <atcoder/all>
#else
#include <mylibs/all.h>
#endif

using ll = long long;
using lll = __int128_t;
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define length(v) ((int)(v).size())
constexpr int inf = 2'000'000'000;
constexpr ll linf = 4'000'000'000'000'000'000, M7 = 1'000'000'007, M9 = 998'244'353;
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using namespace atcoder;

using mint = modint998244353;
constexpr ll MOD = M9;
using mint = static_modint<MOD>;
struct modInv {
    int n;
    vector<mint> d;
    modInv() : n(2), d({0, 1}) {}
    mint operator()(int i) {
        while (n <= i) d.emplace_back(-d[MOD % n] * (MOD / n)), ++n;
        return d[i];
    }
    mint operator[](int i) const { return d[i]; }
} invs;
struct Factorial {
    int n;
    vector<mint> d;
    Factorial() : n(2), d({1, 1}) {}
    mint operator()(int i) {
        while (n <= i) d.emplace_back(d.back() * n), ++n;
        return d[i];
    }
    mint operator[](int i) const { return d[i]; }
} factorial;
struct FactorialInv {
    int n;
    vector<mint> d;
    FactorialInv() : n(2), d({1, 1}) {}
    mint operator()(int i) {
        while (n <= i) d.emplace_back(d.back() * invs(n)), ++n;
        return d[i];
    }
    mint operator[](int i) const { return d[i]; }
} factorialInv;
mint P(int n, int r) {
    if (n < r || n < 0 || r < 0) return 0;
    return factorial(n) * factorialInv(n - r);
}
mint C(int n, int r) {
    if (n < r || n < 0 || r < 0) return 0;
    return factorial(n) * factorialInv(r) * factorialInv(n - r);
}
mint H(int n, int r) {
    const int _n = n + r - 1;
    if (_n < r || _n < 0 || r < 0) return 0;
    return factorial(_n) * factorialInv(r) * factorialInv(_n - r);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;

    vector<vector<mint>> dp = vector<vector<mint>>(n + 1, vector<mint>(n * 2 + 2));
    dp[0][0] = 1;

    rep(i, n) {
        int m = i * 2 + 1;
        rep(j, m) {
            int l = j, r = m - j - 1;
            dp[i + 1][j + 1] += dp[i][j];
            if (j >= 1) dp[i + 1][j + 2] += dp[i][j] * H(l, 2);
            if (j <= m - 2) dp[i + 1][j] += dp[i][j] * H(r, 2);
            if (j != 0 && j != m - 1) dp[i + 1][j + 1] += dp[i][j] * l * r;
        }
    }
    rep(i, 2 * n + 1) cout << dp[n][i].val() << endl;
    return 0;
}
0