Submission #763669

#	Time	Username	Problem	Language	Result	Execution time	Memory
763669		parsadox2	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	454 ms	3212 KiB

ruins3

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 605 , maxl = 1205 , mod = 1e9 + 7;
int n , ar[maxl] , fac[maxl] , dp[maxl][maxn] , f[maxn] , m2[maxn] , frev[maxl];

inline int mpo(int a , int b)
{
	int res = 1;
	while(b != 0)
	{
		if(b & 1)  res = 1LL * res * a % mod;
		b >>= 1;
		a = 1LL * a * a % mod;
	}
	return res;
}

inline int C(int a , int b)
{
	if(b > a || b < 0 || a < 0)  return 0;
	int res = 1LL * fac[a] * frev[b] % mod;
	res = 1LL * res * frev[a - b] % mod;
	return res;
}

int32_t main()
{
	fast;
	cin >> n;
	int m = n * 2;
	for(int i = 0 ; i < n ; i++)
	{
		int x ;  cin >> x;
		ar[x] = 1;
	}
	fac[0] = fac[1] = frev[0] = frev[1] = 1;
	for(int i = 2 ; i < maxl ; i++)
	{
		fac[i] = 1LL * fac[i - 1] * i % mod;
		frev[i] = mpo(fac[i] , mod - 2);
	}
	m2[0] = 1;
	for(int i = 1 ; i < maxn ; i++)  m2[i] = m2[i - 1] * 2 % mod;
	f[0] = 1;
	for(int i = 1 ; i < maxn ; i++)
	{
		for(int j = 0 ; 2 * j <= i ; j++)
		{
			int tmp = (C(2 * j , j) - C(2 * j , j - 1) + mod) % mod;
			tmp = 1LL * tmp * C(i , 2 * j) % mod;
			tmp = 1LL * tmp * m2[i - 2 * j] % mod;
			tmp = 1LL * tmp * fac[i] % mod;
			f[i] = (f[i] + tmp) % mod;
		}
	}

	if(ar[m] == 0)  
	{
		cout << 0 << endl;  return 0;
	}
	int cntz = 0 , cnto = 1;
	dp[m][0] = 1;  dp[m][1] = 2;
	for(int i = m - 1 ; i > 0 ; i--)
	{
		if(ar[i] == 0)  cntz++;
		else cnto++;
		if(ar[i] == 0)
			for(int j = cntz ; j <= cnto ; j++)
				dp[i][j] = 1LL * dp[i + 1][j] * (j - cntz + 1) % mod;
		else
		{
			for(int j = cntz ; j <= cnto ; j++)
			{
				dp[i][j] = dp[i + 1][j];
				for(int k = cntz ; k < j ; k++)
				{
					int tmp = 1LL * f[j - k - 1] * C(cnto - k - 1 , j - k - 1) % mod;
					tmp = 1LL * tmp * (j - k + 1) % mod;
					tmp = 1LL * tmp * dp[i + 1][k] % mod;
					dp[i][j] = (dp[i][j] + tmp) % mod;
				}
			}
		}
	}
	int ans = mpo(m2[n] , mod - 2);
	ans = 1LL * ans * dp[1][n] % mod;
	cout << ans << endl;
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42