제출 #1325792

#제출 시각아이디문제언어결과실행 시간메모리
1325792mopsyarkaBoat (APIO16_boat)C++20
58 / 100
2045 ms16116 KiB
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned ll
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
#define sz(x) (ll)(x.size())
#define pii pair < int, int >
#define pll pair < ll, ll >

#define debug(x) cerr << (#x) << " = " << (x) << endl

const int mod = 1e9 + 7;
const int N = 1001;
const ll OO = 1e18;

template<typename T>
bool umn (T &fi, T se) { return fi > se ? (fi = se, 1) : 0; }

template<typename T>
bool umx (T &fi, T se) { return fi < se ? (fi = se, 1) : 0; }

int a[N], b[N], fac[N], rfac[N];

int dp[N][N], dp1[N][N], p[N][N], p1[N][N], sum[N];

int mul (int x, int y) {
    return 1ll * x * y % mod;
}

int add (int x, int y) {
    x += y;
    if (x >= mod)
        x -= mod;
    return x;
}

int power (int x, int y) {
    if (!y)
        return 1;
    if (y % 2)
        return mul(power(x, y - 1), x);
    int t = power(x, y / 2);
    return mul(t, t);
}

int C (int n, int k) {
    int res = 1;
    for (int i = 1; i <= n; ++i)
        res *= i;
    for (int i = 1; i <= n - k; ++i)
        res /= i;
    for (int i = 1; i <= k; ++i)
        res /= i;
    return res;
}

void slv () {
    int n;
    cin >> n;
    vector < int > v;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        v.pb(a[i] - 1);
        v.pb(b[i]);
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    int ans = 0;
    sum[0] = 1;
    for (int i = 1; i <= n; ++i) {

        for (int j = 1; j < sz(v); ++j) {
            int l = v[j - 1] + 1, r = v[j];
            int cnt = 0;
            int top = 1, fl = 1;
            for (int k = 1; k <= n; ++k) {
                dp1[j][k] = dp[j][k];
                p1[j][k] = p[j][k];
                top = mul(top, r - l + 2 - k);
                if (!(a[i] <= l && r <= b[i]) || k > r - l + 1)
                    continue;
                if (k == 1) {
                    for (int h = 0; h < j; ++h) {
                        dp1[j][k] = add(dp1[j][k], mul(sum[h], r - l + 1));
                        p1[j][k] = add(p1[j][k], sum[h]);
                    }
                } else {
                    dp1[j][k] = add(dp1[j][k], mul(p[j][k - 1], mul(top, rfac[k])));
                    p1[j][k] = add(p1[j][k], p[j][k - 1]);
                }
            }
        }

        for (int j = 1; j < sz(v); ++j) {
            sum[j] = 0;
            for (int k = 0; k <= n; ++k) {
                dp[j][k] = dp1[j][k];
                p[j][k] = p1[j][k];
                dp1[j][k] = p1[j][k] = 0;
                sum[j] = add(sum[j], dp[j][k]);
            }
        }
    }
    for (int i = 1; i < sz(v); ++i) {
        for (int k = 0; k <= n; ++k)
            ans = add(ans, dp[i][k]);
    }
    cout << ans;
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fac[0] = 1;
    for (int i = 1; i < N; ++i)
        fac[i] = mul(i, fac[i - 1]);
    rfac[N - 1] = power(fac[N - 1], mod - 2);
    for (int i = N - 1; i > 0; --i) {
        rfac[i - 1] = mul(rfac[i], i);
    }
    int test = 1;
//    cin >> test;
    while (test--) {
        slv();
        cout << "\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...