Submission #1224320

#TimeUsernameProblemLanguageResultExecution timeMemory
1224320dostsBoat (APIO16_boat)C++17
9 / 100
2096 ms37600 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 2e6+1, inf = 2e9;

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

int mult(int x,int y) {
    return (1LL * x * y) % MOD;
}

int expo(int x,int y) {
    if (!y) return 1;
    int e = expo(x, y >> 1);
    e = mult(e, e);
    if (y & 1) e = mult(e, x);
    return e;
}
int divide(int x, int y) {
    return mult(x, expo(y, MOD - 2));
}
vi f(LIM), finv(LIM);
int nck(int n, int k) {
    if (n < k || n < 0 || k < 0) return 0;
    return mult(f[n], mult(finv[k], finv[n - k]));
}

void combo() {
    f[0] = 1;
    for (int i = 1; i < LIM; i++) f[i] = mult(f[i - 1], i);
    finv[LIM - 1] = divide(1, f[LIM - 1]);
    for (int i = LIM - 2; i >= 0; i--) finv[i] = mult(finv[i + 1], i + 1);
}
int dp[501][1001];
int cfs[501][1001];

void solve() {
    combo();
    int n;
    cin >> n;
    vi a(n+1),b(n+1);
    vi v;
    for (int i=1;i<=n;i++) cin >> a[i] >> b[i];
    for (int i=1;i<=n;i++) v.push_back(a[i]);
    for (int i=1;i<=n;i++) v.push_back(b[i]+1);
    sort(all(v));
    vector<pii> ranges;
    for (int i=1;i<big(v);i++) if (v[i-1] <= v[i]-1) ranges.push_back({v[i-1],v[i]-1});
    if (ranges.empty()) ranges.push_back({a[1],b[1]});
    dp[0][0] = 1;
    vi inv(n+1);
    for (int i=0;i<=n;i++) inv[i] = divide(1,i);
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=big(ranges);j++) {
            pii it = ranges[j-1];
            int sel = 1;
            for (int p = 1;p<=i;p++) {
                sel = mult(sel,it.ss-it.ff+1-p+1);
                sel = mult(sel,inv[p]);
                cfs[i][j] = add(cfs[i][j],mult(sel,nck(i-1,p-1)));
            }
        }
    }
    for (int i=1;i<=n;i++) {
        for (int r = 1;r<=big(ranges);r++) {
            pii it = ranges[r-1];
            if (it.ff >= a[i] && it.ss <= b[i]) {
                for (int j = 0;j<i;j++) {
                    int prvdp = 0;
                    for (int rp = 0;rp<r;rp++) prvdp = add(prvdp,dp[j][rp]);
                    dp[i][r] = add(dp[i][r],mult(prvdp,cfs[i-j][r]));
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1;i<=n;i++) for (int j = 1;j<=big(ranges);j++) ans = add(ans,dp[i][j]);
    cout << ans << '\n';
}   

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...