제출 #1352974

#제출 시각아이디문제언어결과실행 시간메모리
1352974sallyBoat (APIO16_boat)C++20
100 / 100
393 ms4424 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 505;
const ll mod = 1e9 + 7;

int n;

// 區間(已離散)
pair<int,int> seg[N];

// 座標壓縮
vector<int> xs;

// 每一小段長度
int lenv[N * 2];

// DP
ll f[N][N * 2];

// 逆元
ll inv[N + 5];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    xs.push_back(0);

    // 讀入 + 收集座標
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;

        r++; // 轉成 [l, r)

        seg[i] = {l, r};
        xs.push_back(l);
        xs.push_back(r);
    }

    // 離散化
    sort(xs.begin() + 1, xs.end());
    xs.erase(unique(xs.begin() + 1, xs.end()), xs.end());

    int m = (int)xs.size() - 1;

    // 區間轉 index
    for (int i = 1; i <= n; i++) {
        seg[i].first = lower_bound(xs.begin() + 1, xs.end(), seg[i].first) - xs.begin();
        seg[i].second = lower_bound(xs.begin() + 1, xs.end(), seg[i].second) - xs.begin();
    }

    // 每段長度
    for (int i = 1; i < m; i++) {
        lenv[i] = xs[i + 1] - xs[i];
    }

    // 逆元(用來做 /)
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }

    // base case
    for (int j = 0; j <= m; j++) f[0][j] = 1;

    // DP
    for (int i = 1; i <= n; i++) {

        for (int j = seg[i].first; j < seg[i].second; j++) {

            ll C = lenv[j]; // C(r,c)
            int r = lenv[j];
            int c = 1;

            for (int k = i - 1; k >= 0; k--) {

                // 不選 k(或結束於 k)
                f[i][j] = (f[i][j] + f[k][j - 1] * C) % mod;

                // 如果 k 也覆蓋這段 → 加入集合
                if (k > 0 && seg[k].first <= j && j < seg[k].second) {
                    r++;
                    c++;
                    C = C * r % mod * inv[c] % mod;
                }
            }
        }

        // prefix max(保留最佳)
        for (int j = 1; j < m; j++) {
            f[i][j] = (f[i][j] + f[i][j - 1]) % mod;
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + f[i][m - 1]) % mod;
    }

    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...