---
tags: AtCoder, DP, Combinatorics, SPyofgame, kazamahoang
---

AtCoder Beginner Contest 217 F - Make Pair
===

[https://atcoder.jp/contests/abc217/tasks/abc217_f](https://atcoder.jp/contests/abc217/tasks/abc217_f)

---

###### Tags: `DP`, `Combinatorics`.

---
### Hướng dẫn

Nhận thấy, trong một đoạn $[L, R]$ ($L, R$ khác tính chẵn lẻ), việc ghép đôi người ở vị trí $L$ với người ở vị trí $K$ $(L < K \leq R)$ chia đoạn $[L, R]$ ra thành hai đoạn con $[L+1, K-1]$ và $[K+1, R]$. Bên cạnh đó, số cách chọn cặp ghép đôi ở mỗi đoạn con độc lập với nhau.

Ta định nghĩa như sau:
- Kết quả của đoạn $[L+1, K-1]$ là $lf$.
- Kết quả của đoạn $[K+1, R]$ là $rt$.
- Số phép ghép đôi trong đoạn $[L+1, K-1]$ là $X = \frac{K-L-1}{2}$,
- Số phép ghép đôi trong đoạn $[K+1, R]$ là $Y = \frac{R-K}{2}$.

Ta có $lf \times rt$ cách chọn $X+Y$ phép ghép đôi. Trong mỗi cách chọn, lại có ${X+Y+1 \choose Y}$ cách lựa chọn thứ tự của các phép ghép đôi (bao gồm cả phép ghép đôi giữa $L$ và $K$).

Cuối cùng, ta xây dựng được công thức quy hoạch động như sau:
- Gọi $dp[L][R]$ là kết quả nếu xét những người $a_L, a_{L+1}, ..., a_R$
- Gọi $C[N][K] = \binom{N}{K}$ là tổ hợp chập $K$ của $N$
- Công thức: $dp[L][R] = \overset{R}{\underset{k = L+1}{\LARGE \Sigma}} \left(dp[L+1][K-1] \times dp[K+1][R] \times C\left[\frac{K-L-1}{2}+\frac{R-K}{2}+1\right]\left[\frac{R-K}{2} \right] \right)$.
- Cơ sở quy hoạch động:
- Khởi tạo mảng $dp[i][j] = 0$.
- $dp[i][i+1]= 1$.
- Đáp số: $dp[1][2n]$.

---
### Độ phức tạp và cài đặt

Đặt $N = 2 \times n$

Số trạng thái quy hoạch động là $N^2$.
Mỗi trạng thái có chi phí chuyển là $O(N)$.
Ngoài ra việc chuẩn bị mảng tổ hợp mất chi phí là $O(N^2)$.

Vậy tổng độ phức tạp là $O(N^3)$.

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;
using ll = long long;

const int inf = 1061109567;
const ll INF = 4557430888798830399;
const int MOD = 998244353;

int comb[205][205]; // mảng tổ hợp

void init(int n) {
    for (int i = 0; i <= n; ++ i) {
        comb[0][i] = comb[i][i] = 1;
        for (int j = 1; j < i; ++ j)
            comb[j][i] = (comb[j][i-1] + comb[j-1][i-1]) % MOD;
    }
}

int n, m, dp[405][405];
bool good[405][405];

int solve(int l, int r) { // solve for [l, r]
    assert(l <= r + 1);
    if (l > r) return 1;
    int& ret = dp[l][r];
    if (ret != -1) return ret;
    ret = 0; // khởi tạo dp = 0 để tính toán
    for (int k = l + 1; k <= r; ++ k) {
        if (!good[l][k] || (k - l) % 2 == 0) continue;
        // (l, k) được ghép đôi
        int lf = solve(l + 1, k - 1); // solve for [l+1, i-1]
        int rt = solve(k + 1, r); // solve for [i+1, r]
        int cnt_lf = (k - l - 1) / 2 + 1; // (l, i) inclusive
        int cnt_rt = (r - k) / 2;
        ret += (ll)lf * rt % MOD * comb[cnt_lf][cnt_lf+cnt_rt] % MOD;
        ret %= MOD;
    }
    return ret;
}

int32_t main(void) {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        int u, v;
        cin >> u >> v;
        good[u][v] = good[v][u] = true; // good term
    }
    init(n); // khởi tạo mảng tổ hợp
    memset(dp, -1, sizeof dp); // khởi tạo -1 cho việc dp top down
    cout << solve(1, 2 * n) << "\n";
    return 0;
}

// Written by Kazama Hoang ^^