Submission #509805

#	Time	Username	Problem	Language	Result	Execution time	Memory
509805		KoD	Magneti (COCI21_magneti)	C++17	110 / 110	135 ms	4268 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

constexpr int MOD = 1000000007;

struct Fp {
    int x;
    Fp(int x = 0) : x(x) {}
    Fp& operator+=(const Fp& t) {
        if ((x += t.x) >= MOD) x -= MOD;
        return *this;
    }
    Fp& operator*=(const Fp& t) {
        x = (long long)x * t.x % MOD;
        return *this;
    }
    Fp operator+(const Fp& t) const {
        return Fp(*this) += t;
    }
    Fp operator*(const Fp& t) const {
        return Fp(*this) *= t;
    }
    Fp pow(int exp) const {
        Fp ret(1), mul(*this);
        while (exp > 0) {
            if (exp & 1) ret *= mul;
            mul *= mul;
            exp >>= 1;
        }
        return ret;
    }
    Fp inv() const {
        return pow(MOD - 2);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, L;
    std::cin >> N >> L;
    vector<int> R(N);
    for (auto& x : R) {
        std::cin >> x;
    }
    std::sort(R.begin(), R.end());
    vector dp(1, vector<Fp>(L));
    dp[0][0] = 1;
    for (int k = 1; k < N; ++k) {
        vector next(k + 1, vector<Fp>(L));
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < L; ++j) {
                if (j + R[k] < L) {
                    next[i][j + R[k]] += dp[i][j] * (i * 2 + 2);
                }
                if (i > 0 and j + 2 * R[k] < L) {
                    next[i - 1][j + 2 * R[k]] += dp[i][j] * i;
                }
                next[i + 1][j] += dp[i][j] * (i + 2);
            }
        }
        dp = std::move(next);
    }
    vector<Fp> fact(L + 1);
    fact[0] = 1;
    for (int i = 1; i <= L; ++i) {
        fact[i] = fact[i - 1] * i;
    }
    vector<Fp> inv_fact(L + 1);
    inv_fact[L] = fact[L].inv();
    for (int i = L; i >= 1; --i) {
        inv_fact[i - 1] = inv_fact[i] * i;
    }
    const auto binom = [&](const int n, const int r) {
        if (n < r) return Fp(0);
        return fact[n] * inv_fact[r] * inv_fact[n - r];
    };
    Fp ans = 0;
    for (int i = N - 1; i < L; ++i) {
        const int n = L - (i - (N - 1));
        ans += dp[0][i] * binom(n, N);
    }
    std::cout << ans.x << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50