Submission #1352359

#TimeUsernameProblemLanguageResultExecution timeMemory
1352359sallyBoat (APIO16_boat)C++20
0 / 100
2103 ms394856 KiB
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

long long modpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

long long modinv(long long a) { return modpow(a, MOD-2); }

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    static vector<long long> fact(1,1), invfact(1,1);
    while ((int)fact.size() <= n) {
        fact.push_back(fact.back() * (int)fact.size() % MOD);
        invfact.push_back(modinv(fact.back()));
    }
    return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<long long> A(N+1), B(N+1);
    vector<long long> vals;
    for (int i=1;i<=N;i++) {
        cin >> A[i] >> B[i];
        vals.push_back(A[i]);
        vals.push_back(B[i]+1);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    int M = vals.size();
    vector<vector<long long>> dp(N+1, vector<long long>(M));
    vector<vector<long long>> pref(N+1, vector<long long>(M));

    for (int i=1;i<=N;i++) {
        for (int j=0;j<M-1;j++) {
            if (A[i] <= vals[j] && vals[j+1]-1 <= B[i]) {
                long long L = vals[j+1]-vals[j];
                for (int p=1;p<i;p++) {
                    dp[i][j] = (dp[i][j] + pref[p][j-1] * C(L+(i-p)-1, i-p)) % MOD;
                }
            }
        }
        for (int j=0;j<M;j++) {
            pref[i][j] = (dp[i][j] + (j?pref[i][j-1]:0)) % MOD;
        }
    }

    long long ans = 0;
    for (int i=1;i<=N;i++) for (int j=0;j<M;j++) ans = (ans + dp[i][j]) % MOD;
    cout << ans << "\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...