제출 #679241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679241		stevancv	Boat (APIO16_boat)	C++14	27 / 100	1373 ms	3760 KiB

boat

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define sadd(a, b) a = Add(a, b)
#define smul(a, b) a = Mul(a, b)
using namespace std;
const int N = 500 + 2;
const int mod = 1e9 + 7;
int fak[N], inv[N];
int Add(int a, int b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return a;
}
int Mul(int a, int b) {
    ll c = a; c *= b; c %= mod;
    return c;
}
int Exp(int a, int b) {
    int ans = 1;
    while (b > 0) {
        if (b & 1) smul(ans, a);
        smul(a, a);
        b >>= 1;
    }
    return ans;
}
int koef[2 * N][N], dp[2 * N][N];
bool pos[2 * N][N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fak[0] = inv[0] = 1;
    for (int i = 1; i < N; i++) {
        fak[i] = Mul(fak[i - 1], i);
        inv[i] = Exp(fak[i], mod - 2);
    }
    int n; cin >> n;
    vector<int> a(n), b(n), all;
    all.push_back(-1);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        a[i] -= 1;
        all.push_back(a[i]);
        all.push_back(b[i]);
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    int x = all.size();
    for (int i = 1; i < x; i++) {
        int l = all[i] - all[i - 1];
        for (int j = 1; j <= n; j++) {
            int p = l, q = 1;
            for (int k = 1; k <= j; k++) {
                sadd(koef[i][j], Mul(Mul(p, inv[k]), Mul(q, inv[k - 1])));
                smul(p, l - k);
                smul(q, j - k);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
        b[i] = lower_bound(all.begin(), all.end(), b[i]) - all.begin();
    }
    for (int j = 0; j < x; j++) dp[0][j] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = a[i] + 1; j <= b[i]; j++) {
            int y = 1;
            for (int k = i; k >= 0; k--) {
                sadd(dp[i + 1][j], Mul(dp[k][j - 1], koef[j][y]));
                if (pos[j][k - 1]) y += 1;
            }
            pos[j][i] = 1;
        }
        for (int j = 1; j < x; j++) sadd(dp[i + 1][j], dp[i + 1][j - 1]);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) sadd(ans, dp[i][x - 1]);
    cout << ans << en;
    return 0;
}

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