제출 #1325597

#제출 시각아이디문제언어결과실행 시간메모리
1325597mopsyarkaBoat (APIO16_boat)C++20
0 / 100
3 ms2360 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];

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);
}

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());
//    return;
    int ans = 0;
    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;
            if (!(a[i] <= l && r <= b[i]))
                continue;
            int top = 1;
            for (int k = i; k > 0; --k) {
                int o = (a[k] <= l && r <= b[k]);
                if (o) {
                    if (r - l + 1 <= cnt) break;
                    top = mul(top, r - l + 1 - cnt);
                    cnt++;
                    dp[i][j] = add(dp[i][j], mul(top, rfac[cnt]));
                    dp[i][j] = add(dp[i][j], mul(dp[k - 1][j - 1], mul(top, rfac[cnt])));
                }
//                dp[i][j] += (dp[k - 1][j - 1] + 1) * C(r - l + 1, cnt);
            }
//            cout << l << " " << r << "\n" << dp[i][j] << "\n";
        }
        for (int j = 1; j < sz(v); ++j) {
            dp[i][j] = add(dp[i][j], dp[i][j - 1]);
        }
        ans = add(ans, dp[i][sz(v) - 1]);
//        cout << dp[i][sz(v) - 1] << "\n";
    }
    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...