제출 #1282957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282957		stefanneagu	Magneti (COCI21_magneti)	C++20	110 / 110	118 ms	102156 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 51, lmax = 1e4 + 1, mod = 1e9 + 7;
const int comb_max = 1e5 + 1;

int dp[nmax][nmax][lmax];
int v[nmax];

int fact[comb_max];
int inv[comb_max];

int fast(int N, int E) {
    int ans = 1;
    while (E) {
        if (E & 1) {
            ans = (ans * N) % mod;
        }
        N = (N * N) % mod;
        E /= 2;
    }
    return ans;
}

void init() {
    fact[0] = 1;
    for (int i = 1; i < comb_max; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    inv[comb_max - 1] = fast(fact[comb_max - 1], mod - 2);
    for (int i = comb_max - 2; i >= 0; i--) {
        inv[i] = (inv[i + 1] * (i + 1)) % mod;
    }
}

int comb(int n, int k) {
    return ((fact[n] * inv[k]) % mod * inv[n - k]) % mod;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    init();
    int n, l;
    cin >> n >> l;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int grupe = 0; grupe < i; grupe++) {
            for (int len = 0; len < l; len++) {
                // extind o grupa
                if (grupe && len + v[i] <= l) {
                    dp[i][grupe][len + v[i]] = (dp[i][grupe][len + v[i]] + dp[i - 1][grupe][len] * grupe * 2) % mod;
                }
                // fac grupa noua
                if (len + 1 <= l) {
                    dp[i][grupe + 1][len + 1] = (dp[i][grupe + 1][len + 1] + dp[i - 1][grupe][len]) % mod;
                }
                // unesc 2
                if (grupe > 1 && len + 2 * (v[i] - 1) + 1 <= l) {
                    dp[i][grupe - 1][len + 2 * (v[i] - 1) + 1] = (dp[i][grupe - 1][len + 2 * (v[i] - 1) + 1] + dp[i - 1][grupe][len] * grupe * (grupe - 1)) % mod;
                }
            }
        }
    }
    int ans = 0;
    for (int len = 0; len <= l; len++) {
        // l - len items
        // n + 1 boxes
        ans = (ans + comb(l - len + n, n) * dp[n][1][len]) % mod;
    }
    cout << ans << '\n';
    return 0;
}

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