Submission #1186129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186129		dosts	Magneti (COCI21_magneti)	C++17	110 / 110	167 ms	208748 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " << 
using namespace std;

const int N = 3e5+10,MOD = 1e9+7,inf = 2e12;

int add(int x,int y) {
    if (x+y >= MOD) return x+y-MOD;
    return x+y;
}

int mult(int x,int y) {
    return (x*y)%MOD;
}

int expo(int x,int y) {
    if (!y) return 1;
    int e = expo(x,y >> 1);
    e = mult(e,e);
    if (y&1) e = mult(e,x);
    return e;
}

int divide(int x,int y) {
    return mult(x,expo(y,MOD-2));
}

int f[N],finv[N];
int nck(int n,int k) {
    return mult(f[n],mult(finv[k],finv[n-k]));
}

void combo() {
    f[0] = 1;
    for (int i = 1;i<N;i++) f[i] = mult(f[i-1],i);
    finv[N-1] = divide(1,f[N-1]);
    for (int i = N-2;i>=0;i--) finv[i] = mult(finv[i+1],i+1);
    assert(nck(5,3) == 10);
    return;
}
void solve() {
    combo();
    int n,l;
    cin >> n >> l;
    int dp[n+1][n+1][l+1]{};
    vi r(n+1);
    for (int i=1;i<=n;i++) cin >> r[i];
    sort(r.begin()+1,r.end());
    dp[1][1][1] = 1;
    for (int i = 1;i<n;i++) {
        for (int j = 1;j<=i;j++) {
            for (int c = 1;c <= l;c++) {
                if (j < n && c < l) dp[i+1][j+1][c+1] = add(dp[i+1][j+1][c+1],dp[i][j][c]);
                if (c+r[i+1] <= l) dp[i+1][j][c+r[i+1]] = add(dp[i+1][j][c+r[i+1]],mult(dp[i][j][c],2*j));
                if (c+2*r[i+1]-1 <= l) dp[i+1][j-1][c+2*r[i+1]-1] = add(dp[i+1][j-1][c+2*r[i+1]-1],mult(dp[i][j][c],j*(j-1)));
            }
        }
    }
    int ans = 0;
    for (int c = 1;c <= l;c++) ans = add(ans,mult(dp[n][1][c],nck(l-c+n,n)));
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
} 

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