제출 #591723

#제출 시각아이디문제언어결과실행 시간메모리
591723piOOEBoat (APIO16_boat)C++17
100 / 100
526 ms4384 KiB
    //#define _GLIBCXX_DEBUG
     
    //#pragma GCC optimize("Ofast")
    //#pragma GCC optimize("unroll-loops")
    //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
     
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #include <ext/pb_ds/assoc_container.hpp>
     
    using namespace __gnu_pbds;
     
    template<typename T>
    using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;
     
    template<typename T>
    using normal_queue = priority_queue <T, vector<T>, greater<>>;
     
    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
     
    #define ll long long
    #define trace(x) cout << #x << ": " << (x) << endl;
    #define all(x) begin(x), end(x)
    #define rall(x) rbegin(x), rend(x)
    #define uniq(x) x.resize(unique(all(x)) - begin(x))
    #define ld long double
    #define sz(s) ((int) size(s))
    #define pii pair<int, int>
    #define mp(x, y) make_pair(x, y)
    #define int128 __int128
    #define pb push_back
    #define eb emplace_back
     
     
    template<typename T>
    bool ckmin(T &x, T y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }
     
    template<typename T>
    bool ckmax(T &x, T y) {
        if (x < y) {
            x = y;
            return true;
        }
        return false;
    }
     
    int bit(int x, int b) {
        return (x >> b) & 1;
    }
     
    int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
     
    //soryan za musor sverhu
     
    const ll infL = 3e18;
    const int infI = 1'000'000'000 + 7;
    const int N = 1001;
    const ll mod = 1e9 + 7;
    const ld eps = 1e-9;
     
    ll fastp(ll a, ll p) {
        ll ans = 1;
        a %= mod;
        while (p) {
            if (p & 1)
                ans = ans * a % mod;
            a = a * a % mod;
            p >>= 1;
        }
        return ans;
    }
     
    ll fac[N];
    ll invfac[N];
    ll invnum[N];
     
    void init() {
        int n = N - 1;
        fac[0] = invnum[0] = invfac[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fac[i] = fac[i - 1] * i % mod;
        }
        invfac[n] = fastp(fac[n], mod - 2);
        invnum[n] = invfac[n] * fac[n - 1] % mod;
        for (int i = n - 1; i > 0; --i) {
            invfac[i] = invfac[i + 1] * (i + 1) % mod;
            invnum[i] = invfac[i] * fac[i - 1] % mod;
        }
    }
     
    ll inv(ll a) {
        if (a < N) return invnum[a];
        return fastp(a, mod - 2);
    }
     
    ll cnk(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fac[n] * invfac[n - k] % mod * invfac[k] % mod;
    }
     
    ll dp[N][N];
    int A[N], B[N], cord[N];
     
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        init();
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> A[i] >> B[i];
            ++B[i];
            cord[(i - 1) * 2] = A[i];
            cord[(i - 1) * 2 + 1] = B[i];
        }
        sort(cord, cord + n * 2);
        int m = unique(cord, cord + 2 * n) - cord;
        for (int i = 1; i <= n; ++i) {
            A[i] = lower_bound(cord, cord + m, A[i]) - cord + 1;
            B[i] = lower_bound(cord, cord + m, B[i]) - cord + 1;
        }
        for (int i = 0; i < m; ++i) dp[0][i] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = A[i]; j < B[i]; ++j) {
                ll len = cord[j] - cord[j - 1];
                ll x = len;
                int cnt = 1;
                //this number is C(len + cnt - 1, cnt - 1)
                //so when we increase cnt, x = x * (len + cnt - 1) / cnt
                //because the last one is 100% not zero
                for (int k = i - 1; k >= 0; --k) {
                    dp[i][j] = (dp[i][j] + x * dp[k][j - 1]) % mod;
                    if (A[k] <= j && j < B[k]) {
                        ++cnt;
                        x = x * (len + cnt - 1) % mod * inv(cnt) % mod;
                    }
                }
            }
            for (int j = 1; j < N; ++j) {
                dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;
            }
        }
        ll ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans = (ans + dp[i][N - 1]) % mod;
        }
        cout << ans;
        return 0;
     
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...