제출 #1313991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313991		thuhienne	Boat (APIO16_boat)	C++20	0 / 100	10 ms	6200 KiB

boat

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int mod = 1e9 + 7;
const int maxn = 505; // Sửa lại maxn thành 505

int n, a[maxn], b[maxn];
ll inv[maxn];
vector<int> X;
ll dp[maxn][maxn * 2]; // dp[i][j]: trường i chọn thuyền ở khoảng j
ll pref[maxn][maxn * 2]; // pref[i][j]: tổng dp[0..i][0..j]

// Tính nghịch đảo modulo
ll pw(ll a, ll b) {
    ll res = 1; a %= mod;
    while (b > 0) {
        if (b % 2 == 1) res = res * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> n;
    X.push_back(-1); // dummy
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        X.push_back(a[i] - 1);
        X.push_back(b[i]);
    }
    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());

    for (int i = 1; i <= n; i++) inv[i] = pw(i, mod - 2);

    // Khởi tạo: pref[i][j] = 1 nghĩa là có 1 cách để "không chọn gì cả"
    for (int j = 0; j < X.size(); j++) pref[0][j] = 1;

    for (int j = 1; j < (int)X.size(); j++) {
        int L = X[j] - X[j-1];
        if (L <= 0) continue;

        for (int i = 1; i <= n; i++) {
            if (a[i] <= X[j-1] + 1 && b[i] >= X[j]) {
                // Trường i có thể nằm trong khoảng j
                ll combo = L; // Tương đương C(L+1-1, 1)
                int cnt = 1; 
                
                for (int p = i - 1; p >= 0; p--) {
                    // Những cách xếp các trường trước đó ở các khoảng TRƯỚC j
                    ll ways = (pref[p][j-1] * combo) % mod;
                    dp[i][j] = (dp[i][j] + ways) % mod;

                    // Nếu trường p cũng có thể nằm trong khoảng j, tăng cnt
                    if (a[p] <= X[j-1] + 1 && b[p] >= X[j]) {
                        cnt++;
                        // Cập nhật combo: C(L+cnt-1, cnt)
                        // Công thức: C(L+k-1, k) = C(L+k-2, k-1) * (L+k-1) / k
                        combo = combo * (L + cnt - 1) % mod * inv[cnt] % mod;
                    }
                }
            }
        }

        // Cập nhật pref sau khi đã tính xong tất cả i cho khoảng j hiện tại
        for (int i = 1; i <= n; i++) {
            pref[i][j] = (pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + dp[i][j] + mod) % mod;
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < X.size(); j++) ans = (ans + dp[i][j]) % mod;
    }
    cout << ans << endl;

    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42