Submission #521470

#	Time	Username	Problem	Language	Result	Execution time	Memory
521470		errorgorn	Magneti (COCI21_magneti)	C++17	110 / 110	218 ms	24672 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define ub upper_bound
#define lb lower_bound

#define rep(x,s,e) for (int x=s;x!=e;x++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(177013);

const int MOD=1000000007;

ll qexp(ll b,ll p,int m){
    ll res=1;
    while (p){
        if (p&1) res=(res*b)%m;
        b=(b*b)%m;
        p>>=1;
    }
    return res;
}

ll inv(ll i){
	return qexp(i,MOD-2,MOD);
}

ll fix(ll i){
	i%=MOD;
	if (i<0) i+=MOD;
	return i;
}

ll fac[1000005];
ll ifac[1000005];

ll nCk(int i,int j){
	if (i<j) return 0;
	return fac[i]*ifac[j]%MOD*ifac[i-j]%MOD;
}

int n,k;
int arr[55];

ll memo[2][55][10005]; //cc,val

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	fac[0]=1;
	rep(x,1,1000005) fac[x]=fac[x-1]*x%MOD;
	ifac[1000004]=inv(fac[1000004]);
	for (int x=1000004;x>=1;x--) ifac[x-1]=ifac[x]*x%MOD;
	
	cin>>n>>k;
	rep(x,0,n) cin>>arr[x];
	
	if (n==1){
		cout<<k<<endl;
		return 0;
	}
	if (n==2){
		ll space=k-max(arr[0],arr[1])+1;
		if (space<2) cout<<0<<endl;
		else cout<<space*(space-1)<<endl;
		
		return 0;
	}
	
	sort(arr,arr+n);
	
	int a=0,b=1;
	memo[a][0][0]=1;
	rep(i,0,n){
		memset(memo[b],0,sizeof(memo[b]));
		
		rep(x,0,50) rep(y,0,10005){
			memo[b][x+1][y]=(memo[b][x+1][y]+(x+1)*memo[a][x][y])%MOD;
			if (y+arr[i]<=k)
				memo[b][x][y+arr[i]]=(memo[b][x][y+arr[i]]+memo[a][x][y]*2*x)%MOD;
			if (x>=2 && y+arr[i]*2<=k)
				memo[b][x-1][y+2*arr[i]]=(memo[b][x-1][y+2*arr[i]]+memo[a][x][y]*(x-1))%MOD;
		}
		swap(a,b);
	}
	
	ll ans=0;
	rep(l,0,10005) if (memo[a][1][l]){
		ans=(ans+nCk(k-l+(n-1),n)*memo[a][1][l])%MOD;
		//cout<<l<<" "<<memo[a][1][l]<<endl;
	}
	
	cout<<ans%MOD<<endl;
}

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