Submission #868919

#	Time	Username	Problem	Language	Result	Execution time	Memory
868919		Cyber_Wolf	Magneti (COCI21_magneti)	C++17	110 / 110	279 ms	199848 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define lg long long 

const lg N = 2e5+5, MOD = 1e9+7;

lg v[N], fact[N];

lg fast_power(lg n, lg k)
{
	lg ans = 1;
	while(k)
	{
		if((k&1))
		{
			ans = (ans*n)%MOD;
		}
		n = (n*n)%MOD;
		k >>= 1;
	}
	return ans;
}

lg C(lg n, lg r)
{
	lg ans = fact[n];
	ans = (ans*fast_power(fact[r], MOD-2))%MOD;
	ans = (ans*fast_power(fact[n-r], MOD-2))%MOD;
	return ans;
}

lg dp[51][51][int(1e4+5)], fr[int(1e4+5)];

int main()
{
	lg n, l;
	cin >> n >> l;
	fact[0] = 1;
	for(lg i = 1; i <= 1e5; i++)	fact[i] = (fact[i-1]*i)%MOD;
	for(int i = 1; i <= n; i++)	cin >> v[i];
	sort(v+1, v+n+1);
	dp[1][1][1] = 1;
	for(int i = 1; i < n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			for(int k = 0; k <= l; k++)
			{
				if(k+v[i+1] <= 1e4)	dp[i+1][j][k+v[i+1]] = (dp[i+1][j][k+v[i+1]]+(dp[i][j][k]*j*2ll)%MOD)%MOD;
				if(j && k+v[i+1]*2 <= 1e4)	
				{
					dp[i+1][j-1][k+v[i+1]*2] = (dp[i+1][j-1][k+v[i+1]*2]+(dp[i][j][k]*(j*(j-1))%MOD)%MOD)%MOD;
				}
				dp[i+1][j+1][k] = (dp[i+1][j+1][k]+dp[i][j][k])%MOD; 
			}
		}
	}
	for(int i = 0; i <= l; i++)	fr[i] = dp[n][1][i];
	lg ans = 0;
	for(lg i = 0; i <= l; i++)
	{
		lg cur = fr[i];
		// cout << cur << ' ' << l-i+n << ' ' << n << '\n';
		cur = (cur*C(l-i+n, n))%MOD;
		ans = (ans+cur)%MOD;
	}
	cout << ans << '\n';
}

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