Submission #1281139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281139		jioung	Boat (APIO16_boat)	C++20	100 / 100	1620 ms	6428 KiB

boat

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

void addmod(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}
int mulmod(int a, int b) { return (int)((1LL * a * b) % MOD); }

int dp[2][1005][505];
int n;
int a[505], b[505];
int sz[1005];        
long long sz1[1005];
int Ctab[1005][505];
int tot[1005];
vector<long long> comp;
ll inv_int[505];

ll comb_large(ll G, int k) {
    if (k < 0) return 0;
    if (k == 0) return 1;
    if (G < k) return 0;
    ll res = 1;
    for (int i = 1; i <= k; ++i) {
        ll num = (G - i + 1) % MOD;
        if (num < 0) num += MOD;
        res = (res * num) % MOD;
        res = (res * inv_int[i]) % MOD;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n)) return 0;

    comp.clear();
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        comp.push_back(a[i]);
        comp.push_back((long long)b[i] + 1);
    }
    comp.push_back(0);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());

    int M = (int)comp.size() - 1;

    for (int i = 0; i <= M; ++i) {
        if (i < M) {
            ll G = comp[i+1] - comp[i];
            sz1[i] = G;
            sz[i] = (int)min<ll>(G, n); 
        } else {
            sz1[i] = 1;
            sz[i] = 1;
        }
    }
    inv_int[0] = 0;
    for (int i = 1; i <= n; ++i) inv_int[i] = modpow(i, MOD - 2);
    for (int i = 0; i <= M; ++i) {
        Ctab[i][0] = 1;
        for (int len = 1; len <= sz[i]; ++len) {
            Ctab[i][len] = (int)comb_large(sz1[i], len);
        }
    }
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        int cur = i & 1;
        int prv = cur ^ 1;
        for (int j = 0; j <= M; ++j) for (int len = 0; len <= sz[j]; ++len) dp[cur][j][len] = 0;

        for (int j = 0; j <= M; ++j) {
            for (int len = 0; len <= sz[j]; ++len) {
                if (dp[prv][j][len]) addmod(dp[cur][j][len], dp[prv][j][len]);
            }
        }
        int L = int(lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin());
        int R = int(lower_bound(comp.begin(), comp.end(), (long long)b[i] + 1) - comp.begin() - 1);
        if (R < L) {
            continue;
        }
        for (int t = 0; t <= R; ++t) tot[t] = 0;
        for (int k = 0; k <= R; ++k) {
            if (k > 0) tot[k] = tot[k-1];
            else tot[k] = 0;
            for (int len = 0; len <= sz[k]; ++len) {
                if (dp[prv][k][len] == 0) continue;
                addmod(tot[k], mulmod(dp[prv][k][len], Ctab[k][len]));
            }
        }
        for (int j = L; j <= R; ++j) {
            for (int len = 0; len < sz[j]; ++len) {
                if (dp[prv][j][len] == 0) continue;
                addmod(dp[cur][j][len+1], dp[prv][j][len]);
            }
            int prev_tot = (j == 0 ? 0 : tot[j-1]);
            if (prev_tot) addmod(dp[cur][j][1], prev_tot);
        }

        for (int j = 0; j <= M; ++j) for (int len = 0; len <= sz[j]; ++len) dp[prv][j][len] = 0;
    }
    int ans = 0;
    int last = n & 1;
    for (int j = 0; j <= M; ++j) {
        for (int len = 0; len <= sz[j]; ++len) {
            if (dp[last][j][len] == 0) continue;
            addmod(ans, mulmod(dp[last][j][len], Ctab[j][len]));
        }
    }
    ans = (ans - 1) % MOD;
    if (ans < 0) ans += MOD;
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42