Submission #25583549

Source Code Expand

#line 1 "main.cpp"
#include <bits/stdc++.h>
#line 2 "/home/ubuntu/Library/utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 4 "/home/ubuntu/Library/modulus/modpow.hpp"

inline int32_t modpow(uint_fast64_t x, uint64_t k, int32_t MOD) {
    assert (/* 0 <= x and */ x < (uint_fast64_t)MOD);
    uint_fast64_t y = 1;
    for (; k; k >>= 1) {
        if (k & 1) (y *= x) %= MOD;
        (x *= x) %= MOD;
    }
    assert (/* 0 <= y and */ y < (uint_fast64_t)MOD);
    return y;
}
#line 5 "/home/ubuntu/Library/modulus/modinv.hpp"

inline int32_t modinv_nocheck(int32_t value, int32_t MOD) {
    assert (0 <= value and value < MOD);
    if (value == 0) return -1;
    int64_t a = value, b = MOD;
    int64_t x = 0, y = 1;
    for (int64_t u = 1, v = 0; a; ) {
        int64_t q = b / a;
        x -= q * u; std::swap(x, u);
        y -= q * v; std::swap(y, v);
        b -= q * a; std::swap(b, a);
    }
    if (not (value * x + MOD * y == b and b == 1)) return -1;
    if (x < 0) x += MOD;
    assert (0 <= x and x < MOD);
    return x;
}

inline int32_t modinv(int32_t x, int32_t MOD) {
    int32_t y = modinv_nocheck(x, MOD);
    assert (y != -1);
    return y;
}
#line 6 "/home/ubuntu/Library/modulus/mint.hpp"

/**
 * @brief quotient ring / 剰余環 $\mathbb{Z}/n\mathbb{Z}$
 */
template <int32_t MOD>
struct mint {
    int32_t value;
    mint() : value() {}
    mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {}
    mint(int32_t value_, std::nullptr_t) : value(value_) {}
    explicit operator bool() const { return value; }
    inline mint<MOD> operator + (mint<MOD> other) const { return mint<MOD>(*this) += other; }
    inline mint<MOD> operator - (mint<MOD> other) const { return mint<MOD>(*this) -= other; }
    inline mint<MOD> operator * (mint<MOD> other) const { return mint<MOD>(*this) *= other; }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; }
    inline mint<MOD> operator - () const { return mint<MOD>(this->value ? MOD - this->value : 0, nullptr); }
    inline bool operator == (mint<MOD> other) const { return value == other.value; }
    inline bool operator != (mint<MOD> other) const { return value != other.value; }
    inline mint<MOD> pow(uint64_t k) const { return mint<MOD>(modpow(value, k, MOD), nullptr); }
    inline mint<MOD> inv() const { return mint<MOD>(modinv(value, MOD), nullptr); }
    inline mint<MOD> operator / (mint<MOD> other) const { return *this * other.inv(); }
    inline mint<MOD> & operator /= (mint<MOD> other) { return *this *= other.inv(); }
};
template <int32_t MOD> mint<MOD> operator + (int64_t value, mint<MOD> n) { return mint<MOD>(value) + n; }
template <int32_t MOD> mint<MOD> operator - (int64_t value, mint<MOD> n) { return mint<MOD>(value) - n; }
template <int32_t MOD> mint<MOD> operator * (int64_t value, mint<MOD> n) { return mint<MOD>(value) * n; }
template <int32_t MOD> mint<MOD> operator / (int64_t value, mint<MOD> n) { return mint<MOD>(value) / n; }
template <int32_t MOD> std::istream & operator >> (std::istream & in, mint<MOD> & n) { int64_t value; in >> value; n = value; return in; }
template <int32_t MOD> std::ostream & operator << (std::ostream & out, mint<MOD> n) { return out << n.value; }
#line 4 "/home/ubuntu/Library/modulus/factorial.hpp"

template <int32_t MOD>
mint<MOD> fact(int n) {
    static std::vector<mint<MOD> > memo(1, 1);
    while (n >= memo.size()) {
        memo.push_back(memo.back() * mint<MOD>(memo.size()));
    }
    return memo[n];
}
template <int32_t MOD>
mint<MOD> inv_fact(int n) {
    static std::vector<mint<MOD> > memo;
    if (memo.size() <= n) {
        int l = memo.size();
        int r = n * 1.3 + 100;
        memo.resize(r);
        memo[r - 1] = fact<MOD>(r - 1).inv();
        for (int i = r - 2; i >= l; -- i) {
            memo[i] = memo[i + 1] * (i + 1);
        }
    }
    return memo[n];
}
#line 5 "/home/ubuntu/Library/modulus/choose.hpp"

/**
 * @brief combination / 組合せ ${} _ n C _ r$ (前処理 $O(n)$ + $O(1)$)
 */
template <int32_t MOD>
mint<MOD> choose(int n, int r) {
    assert (0 <= r and r <= n);
    return fact<MOD>(n) * inv_fact<MOD>(n - r) * inv_fact<MOD>(r);
}
#line 5 "main.cpp"
using namespace std;

constexpr int64_t MOD = 998244353;
mint<MOD> solve(int64_t n, int m, const std::vector<int64_t> &a, const std::vector<int64_t> &b) {
    vector<vector<bool>> g(2 * n, vector<bool>(2 * n));
    REP (i, m) {
        g[a[i]][b[i]] = true;
        g[b[i]][a[i]] = true;
    }

    vector<vector<mint<MOD>>> dp0(2 * n + 1, vector<mint<MOD>>(2 * n + 1));  // zero or more pairs of parens
    vector<vector<mint<MOD>>> dp1(2 * n + 1, vector<mint<MOD>>(2 * n + 1));  // just one pair of parens
    REP (i, 2 * n + 1) {
        dp0[i][i] += 1;
    }
    REP3 (len, 2, 2 * n + 1) {
        if (len % 2 != 0) {
            continue;
        }
        REP (l, 2 * n + 1 - len) {
            int r = l + len;
            if (g[l][r - 1]) {
                dp0[l][r] += dp0[l + 1][r - 1];
                dp1[l][r] = dp0[l][r];
            }
            for (int m = l + 2; m < r; m += 2) {
                dp0[l][r] += dp0[l][m] * dp1[m][r] * choose<MOD>(len / 2, (m - l) / 2);
            }
// if(dp0[l][r])cerr << l << "," << r << ": " << dp0[l][r]<<endl;
        }
    }
    return dp0[0][2 * n];
}

// generated by oj-template v4.8.0 (https://github.com/online-judge-tools/template-generator)
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int64_t N;
    int M;
    std::cin >> N >> M;
    std::vector<int64_t> A(M), B(M);
    REP (i, M) { std::cin >> A[i] >> B[i]; -- A[i]; -- B[i]; }
    auto ans = solve(N, M, A, B);
    std::cout << ans << '\n';
    return 0;
}

Submission Info

Submission Time
Task F - Make Pair
User kimiyuki
Language C++ (GCC 9.2.1)
Score 500
Code Size 6344 Byte
Status AC
Exec Time 63 ms
Memory 5788 KiB

Compile Error

/home/ubuntu/Library/modulus/factorial.hpp: In instantiation of ‘mint<MOD> fact(int) [with int MOD = 998244353]’:
/home/ubuntu/Library/modulus/choose.hpp:12:21:   required from ‘mint<MOD> choose(int, int) [with int MOD = 998244353]’
main.cpp:31:86:   required from here
/home/ubuntu/Library/modulus/factorial.hpp:8:14: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<mint<998244353> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
/home/ubuntu/Library/modulus/factorial.hpp: In instantiation of ‘mint<MOD> inv_fact(int) [with int MOD = 998244353]’:
/home/ubuntu/Library/modulus/choose.hpp:12:40:   required from ‘mint<MOD> choose(int, int) [with int MOD = 998244353]’
main.cpp:31:86:   required from here
/home/ubuntu/Library/modulus/factorial.hpp:16:21: warning: comparison of integer expressions of different signedness: ‘std::vector<mint<998244353> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 28
Set Name Test Cases
Sample example_00.txt, example_01.txt, example_02.txt
All example_00.txt, example_01.txt, example_02.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt
Case Name Status Exec Time Memory
example_00.txt AC 6 ms 3624 KiB
example_01.txt AC 2 ms 3580 KiB
example_02.txt AC 1 ms 3556 KiB
hand_00.txt AC 63 ms 5788 KiB
hand_01.txt AC 51 ms 5296 KiB
hand_02.txt AC 50 ms 4948 KiB
hand_03.txt AC 52 ms 4908 KiB
hand_04.txt AC 47 ms 4904 KiB
hand_05.txt AC 3 ms 3620 KiB
hand_06.txt AC 2 ms 3624 KiB
random_00.txt AC 47 ms 4880 KiB
random_01.txt AC 55 ms 4916 KiB
random_02.txt AC 54 ms 4904 KiB
random_03.txt AC 51 ms 4996 KiB
random_04.txt AC 54 ms 5484 KiB
random_05.txt AC 4 ms 3692 KiB
random_06.txt AC 49 ms 4748 KiB
random_07.txt AC 55 ms 5220 KiB
random_08.txt AC 59 ms 5540 KiB
random_09.txt AC 49 ms 4784 KiB
random_10.txt AC 3 ms 3648 KiB
random_11.txt AC 55 ms 4988 KiB
random_12.txt AC 49 ms 5004 KiB
random_13.txt AC 54 ms 4900 KiB
random_14.txt AC 56 ms 5052 KiB
random_15.txt AC 2 ms 3620 KiB
random_16.txt AC 57 ms 5048 KiB
random_17.txt AC 51 ms 4844 KiB