Submission #541156

#	Time	Username	Problem	Language	Result	Execution time	Memory
541156		AlperenT	Magneti (COCI21_magneti)	C++17	110 / 110	201 ms	118892 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 50 + 5, S = 1e4 + 5, MOD = 1e9 + 7;

struct mint{
    int val = 0;
 
    mint(long long a = 0) : val(a % MOD) {if(val < 0) val += MOD; }
    mint(long long a, long long b) {*this += a; *this /= b; }
 
    mint &operator += (const mint &b) {val += b.val; if(val >= MOD) val -= MOD; return *this; }
    mint &operator -= (const mint &b) {val -= b.val; if(val < 0) val += MOD; return *this; }
    mint &operator *= (const mint &b) {val = (1ll * val * b.val) % MOD; return *this; }
 
    mint mexp(mint a, long long b){
        mint c(1);
        for(; b > 0; b /= 2, a *= a) if(b & 1) c *= a;
        return c;
    }
 
    mint minv(const mint &a) {return mexp(a, MOD - 2); };
 
    mint &operator /= (const mint &b) {*this *= minv(b); return *this; }
 
    friend mint operator + (mint a, const mint &b) {return a += b; }
    friend mint operator - (mint a, const mint &b) {return a -= b; }
    friend mint operator - (const mint &a) {return 0 - a; }
    friend mint operator * (mint a, const mint &b) {return a *= b; }
    friend mint operator / (mint a, const mint &b) {return a /= b; }
 
    friend bool operator == (const mint &a, const mint &b) {return a.val == b.val; }
    friend bool operator != (const mint &a, const mint &b) {return a.val != b.val; }
 
    friend istream &operator >> (istream &is, mint &a) {long long b; is >> b; a = b; return is; }
    friend ostream &operator << (ostream &os, const mint &a) {return os << a.val; }
};

int n, m, arr[N];

mint dp[N][N][S], fa[S], invfa[S], ans;

void precalc(){
    fa[0] = 1;
    for(int i = 1; i < S; i++) fa[i] = fa[i - 1] * i;

    invfa[S - 1] = mint().minv(fa[S - 1]);
    for(int i = S - 2; i >= 0; i--) invfa[i] = invfa[i + 1] * (i + 1);
}

mint calc(int stars, int bars){
    return fa[bars + stars] * (invfa[bars] * invfa[stars]);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    precalc();

    cin >> n >> m;

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

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

    dp[0][0][0] = 1;

    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            for(int k = 0; k <= m; k++){
                if(k + 1 <= m) dp[i + 1][j + 1][k + 1] += dp[i][j][k];
                if(k + arr[i + 1] <= m && j >= 1) dp[i + 1][j][k + arr[i + 1]] += dp[i][j][k] * j * 2;
                if(k + (arr[i + 1] * 2 - 1) <= m && j >= 2) dp[i + 1][j - 1][k + (arr[i + 1] * 2 - 1)] += dp[i][j][k] * j * (j - 1);
            }
        }
    }

    for(int i = 0; i <= m; i++) ans += dp[n][1][i] * calc(m - i, n);

    cout << ans;
}

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