Submission #376463

#	Time	Username	Problem	Language	Result	Execution time	Memory
376463		KoD	Boat (APIO16_boat)	C++17	9 / 100	706 ms	6704 KiB

boat

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

constexpr int MOD = 1000000007;

struct Fp {
    int val;
    Fp(const int val = 0): val(((val % MOD) + MOD) % MOD) { }
    Fp& operator += (const Fp &other) {
        if ((val += other.val) >= MOD) val -= MOD;
        return *this;
    }
    Fp operator + (const Fp &other) const {
        return Fp(*this) += other;
    }
    Fp& operator -= (const Fp &other) {
        if ((val += MOD - other.val) >= MOD) val -= MOD;
        return *this;
    }
    Fp operator - (const Fp &other) const {
        return Fp(*this) -= other;
    }
    Fp& operator *= (const Fp &other) {
        val = (long long) val * other.val % MOD;
        return *this;
    }
    Fp operator * (const Fp &other) const {
        return Fp(*this) *= other;
    }
    Fp& operator /= (const Fp &other) {
        return *this *= other.inv();
    }
    Fp operator / (const Fp &other) const {
        return Fp(*this) /= other;
    }
    Fp inv() const {
        return pow(MOD - 2);
    }
    Fp pow(int e) const {
        Fp ret(1), mult(*this);
        while (e > 1) {
            if (e & 1) ret *= mult;
            mult *= mult;
            e >>= 1;
        }
        return ret;
    }
};

int main() {
    int N;
    std::cin >> N;
    Vec<int> A(N), B(N);
    Vec<int> cmp;
    cmp.reserve(2 * N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i] >> B[i];
        B[i] += 1;
        cmp.push_back(A[i]);
        cmp.push_back(B[i]);
    }
    std::sort(cmp.begin(), cmp.end());
    cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
    for (auto &x: A) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    for (auto &x: B) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    const auto size = (int) cmp.size() - 1;
    Vec<Vec<Fp>> coeff(size, Vec<Fp>(N + 1));
    for (int k = 0; k < size; ++k) {
        Fp val(cmp[k + 1] - cmp[k]);
        for (int j = 1; j <= N; ++j) {
            if (cmp[k + 1] - cmp[k] < j) {
                break;
            }
            coeff[k][j] = val;
            val *= Fp(cmp[k + 1] - cmp[k] - j);
            val /= Fp(j + 1);
        }
    }
    Vec<Vec<Fp>> dp(size, Vec<Fp>(N + 1));
    for (int k = 0; k < size; ++k) {
        dp[k][0] = Fp(1);
    }
    Fp ans;
    for (int i = 0; i < N; ++i) {
        Vec<Vec<Fp>> next(size, Vec<Fp>(N + 1));
        Fp sum;
        for (int k = 0; k < size; ++k) {
            next[k][0] += sum;
            for (int j = 0; j <= N; ++j) {
                if (dp[k][j].val == 0) {
                    continue;
                }
                next[k][j] += dp[k][j];
                if (A[i] <= k && k < B[i]) {
                    next[k][j + 1] += dp[k][j];
                    const auto end = dp[k][j] * coeff[k][j + 1];
                    ans += end;
                    sum += end;
                }
            }
        }
        dp = std::move(next);
    }
    std::cout << ans.val << '\n';
    return 0;
}

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