제출 #855913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855913		wakandaaa	Magneti (COCI21_magneti)	C++17	110 / 110	105 ms	121876 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int inf = 1e9; // INT_MAX;
const long long llinf = 1e18; // LLONG_MAX;

template<class X, class Y>
bool minimize(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}

template<class X, class Y>
bool maximize(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}

template<class X, class Y>
bool add(X &a, Y b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return true;
}

const int MAX_N = 50 + 5;
const int MAX_L = 1e4 + 5;

int n, l;
int a[N];
int f[MAX_N][MAX_N][MAX_L];

int pw(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) res = 1LL * res * x % mod;
        x = 1LL * x * x % mod;
        y >>= 1;
    }
    return res % mod;
}
int fac[N], inv[N];
void pre() {
    int n = 1e6;
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = 1LL * fac[i - 1] * i % mod;
    inv[n] = pw(fac[n], mod - 2);
    for (int i = n; i >= 1; --i) inv[i - 1] = 1LL * inv[i] * i % mod;
}
int nCk(int n, int k) {
    if (k > n || k < 0) return 0;
    return 1LL * fac[n] * inv[k] % mod * inv[n - k] % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    pre();

    cin >> n >> l;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    sort(a + 1, a + n + 1);

    f[0][0][0] = 1;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            for (int k = 1; k <= l; ++k) {
                int r = a[i];
                // new component
                f[i][j][k] = f[i - 1][j - 1][k - 1];

                // append
                if (k - r >= 0)
                    add(f[i][j][k], 1LL * f[i - 1][j][k - r] * 2 * j % mod);
                
                // join
                // (r - 1) + (r - 1) + 1 = 2r - 1
                if (k - 2 * r + 1 >= 0)
                    add(f[i][j][k], 1LL * f[i - 1][j + 1][k - 2 * r + 1] * j * (j + 1) % mod);
            }

    int res = 0;
    for (int i = 1; i <= l; ++i)
        add(res, 1LL * f[n][1][i] * nCk(n + l - i, n) % mod);

    cout << res;

    return 0;
}

/*

*/

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