Submission #406637

#TimeUsernameProblemLanguageResultExecution timeMemory
406637gevacrtBoat (APIO16_boat)C++17
9 / 100
2101 ms163364 KiB
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define int ll

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

int MULT(){return 1;}
template<typename T, typename... Args>
int MULT(T v, Args... args){
    return (v*MULT(args...))%MOD;
}

int binexp(int base, int pow, int M=MOD){
    int res = 1;
    while(pow){
        if(pow & 1) res *= base;
        pow >>= 1, base *= base;
        if(M) base %= M, res %= M;
    }
    return res;
}
constexpr int fac(int n){
    if(n == 0) return 1;
    return MULT(n, fac(n-1));
}
int nCk(int n, int k){
    return MULT(fac(n), binexp(fac(k), MOD-2), binexp(fac(n-k), MOD-2));    
}

vii A; vi B; vvi dp;

int solve(int n, int c){
    if(n == -1) return 1;
    if(c == 0) return 1;
    if(dp[n][c] != -1)
        return dp[n][c];

    auto &v = dp[n][c]; v = solve(n, c-1);

    for(int x = n, cnt = 0; x >= 0; x--){
        if(!(A[x].first <= B[c-1] and B[c] <= A[x].second))
            continue;
    
        for(int k = 0; k <= min(cnt, B[c]-B[c-1]-1); k++)
            v += MULT(nCk(B[c]-B[c-1], k+1), nCk(cnt, k), solve(x-1, c-1)), v %= MOD;

        cnt++;
    }

    return v;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N; cin >> N;

    A.resize(N);
    for(auto &[l, r] : A){
        cin >> l >> r; r++;    
        B.push_back(l); B.push_back(r);
    }

    sort(all(B));

    dp.resize(N, vi(B.size(), -1));
    cout << solve(N-1, B.size()-1)-1 << endl;

    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...