Submission #25638211

---

Source Code Expand

// {{{
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define debug(x...)
#define debug_arr(x...)
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// }}}

// clang-format off
struct Comb {
    int l, mod; vector<LL> f, inv, finv;
    Comb(int _n, int m = 1e9 + 7) : l(_n), mod(m) {
        f.resize(l + 1), inv.resize(l + 1), finv.resize(l + 1);
        inv[1] = f[0] = f[1] = finv[0] = finv[1] = 1;
        for (int i = 2; i <= l; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
        for (int i = 2; i <= l; ++i) f[i] = f[i - 1] * i % mod;
        for (int i = 2; i <= l; ++i) finv[i] = finv[i - 1] * inv[i] % mod;
    }

    LL ncr(int n, int m) {
        if (m < 0 || m > n) return 0;
        return f[n] * finv[m] % mod * finv[n - m] % mod;
    }
};  // clang-format on

const int mod = 998244353;
const int N = 410;
Comb comb(N, mod);

LL dp[N][N];
set<int> g[N];
int n, m;

LL dfs(int l, int r)
{
    // debug(l, r);
    if (dp[l][r] != -1) return dp[l][r];
    if (l - 1 == r) return dp[l][r] = 1;
    if ((r - l + 1) % 2 == 1) return dp[l][r] = 0;

    LL ret = 0;
    int c = (r - l + 1) / 2;

    for (int p = l + 1; p <= r; p += 2)
    {
        if (g[l].find(p) == g[l].end()) continue;
        int a = (p - 1 - (l + 1) + 1) / 2;
        int b = (r - (p + 1) + 1) / 2;
        assert(a + b + 1 == c);
        // [l, p]; [l +1 , p -1];
        // [p + 1, r]
        LL cb = comb.ncr(c, b);

        LL va = dfs(l + 1, p - 1);
        LL vb = dfs(p + 1, r);
        if (va == 0 || vb == 0) continue;
        LL v = cb * vb % mod * va % mod;
        ret = (ret + v) % mod;
    }

    // debug(l, r, ret);

    return dp[l][r] = ret;
}

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif

    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n >> m)
    {
        for (int i = 1; i <= n; ++i) g[i].clear();
        for (int i = 1; i <= m; ++i)
        {
            int a, b;
            cin >> a >> b;
            g[a].insert(b);
        }
        // for (int i = 1; i <= n; ++i) sort(all(g[i]));

        clr(dp, -1);
        LL ans = dfs(1, 2 * n);
        cout << ans << '\n';
    }

    return 0;
}

Submission Info

Judge Result