Learning Algorithms

アルゴリズムの勉強メモ

AGC 028 D. Chords

D - Chords

まず円を直線上に展開することに気付くと,区間を $N$ 個とる問題になって区間 $dp$ っぽいことができそうな気持ちになります.連結成分を適当に分けてそれぞれ独立に数え上げることができればよさそうなことから自然に $dp(l, r) :=$ 区間 $[l, r]$ を被覆する連結成分の数 が生えて,これは $O(N^3)$ で計算できるので,これで解けました

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; (i) < (int) (n); (i) ++)
using namespace std;

int main() {
        int n, k;
        scanf("%d%d", &n, &k);
        vector<int> p(2 * n, -1);
        rep(i, k) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                p[a] = b;
                p[b] = a;
        }
        vector<vector<long long>> tozan(2 * n, vector<long long> (2 * n));
        rep(i, 2 * n) {
                rep(j, 2 * n) {
                        for (int l = i; l <= j; l ++) {
                                tozan[i][j] += (p[l] == -1);
                        }
                }
        }
        const long long mod = 1e9 + 7;
        vector<vector<long long>> gezan(2 * n, vector<long long> (2 * n));
        rep(i, 2 * n) {
                rep(j, 2 * n) {
                        if (tozan[i][j] % 2 == 0) {
                                gezan[i][j] = 1;
                                for (long long l = tozan[i][j] - 1; l > 0; l -= 2) {
                                        (gezan[i][j] *= l) %= mod;
                                }
                        }
                }
        }
        vector<vector<long long>> dp(2 * n, vector<long long> (2 * n));
        vector<long long> hoge;
        long long ans = 0;
        for (int d = 1; d < 2 * n; d ++) {
                rep(l, 2 * n) {
                        int r = l + d;
                        if (r >= 2 * n) break;
                        bool ng = false;
                        for (int m = l; m <= r; m ++) {
                                if (p[m] != -1 && (p[m] < l || r < p[m])) {
                                        ng = true;
                                        break;
                                }
                        }
                        if (tozan[l][r] % 2 == 1) ng = true;
                        if (ng) continue;
                        dp[l][r] = gezan[l][r];
                        for (int m = l + 1; m < r; m ++) {
                                (dp[l][r] -= dp[l][m] * gezan[m + 1][r] % mod) %= mod;
                                (dp[l][r] += mod) %= mod;
                        }
                        long long rem = (l > 0 ? tozan[0][l - 1] : 0) + (r < 2 * n - 1 ? tozan[r + 1][2 * n - 1] : 0);
                        long long unko = 1;
                        for (long long m = rem - 1; m > 0; m -= 2) (unko *= m) %= mod;
                        (ans += dp[l][r] * unko % mod) %= mod;
                }
        }
        printf("%lld\n", ans);
        return 0;
}