Submission #527638

#	Time	Username	Problem	Language	Result	Execution time	Memory
527638		pooyashams	Ruins 3 (JOI20_ruins3)	C++14	100 / 100	466 ms	11640 KiB

ruins3

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 1210;
const int mod = 1e9+7;

inline int bpow(int x, int y)
{
	int ans = 1;
	while(y > 0)
	{
		if(y & 1)
			ans = 1ll*ans*x % mod;
		x = 1ll*x*x % mod;
		y >>= 1;
	}
	return ans;
}

int MK(int a, int b)
{
	a += b;
	if(a >= mod) return a-mod;
	if(a < 0) return a+mod;
	return a;
}


int dp[maxn];
int prf[maxn][maxn];
int cmb[maxn][maxn];
bool one[maxn];

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cmb[0][0] = 1;
	for(int i = 1; i < maxn; i++)
	{
		cmb[i][0] = 1;
		for(int j = 1; j <= i; j++)
			cmb[i][j] = MK(cmb[i-1][j], cmb[i-1][j-1]);
	}
	int n; cin >> n;
	for(int i = 0; i < n; i++)
	{
		int x; cin >> x; x--;
		one[x] = true;
	}
	dp[0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < i; j++)
			dp[i] = MK(dp[i], 1ll*dp[j]*dp[i-1-j]%mod * cmb[i-1][j]%mod * (i-j+1) % mod );
	prf[2*n][0] = 1;
	int c1 = 0;
	for(int i = 2*n-1; i >= 0; i--)
	{
		c1 += one[i];
		if(one[i])
		{
			for(int j = 0; j <= c1; j++)
			{
				prf[i][j] = prf[i+1][j];
				for(int k = 0; k < j; k++)
				{
					prf[i][j] = MK(prf[i][j], 1ll*prf[i+1][k]*dp[j-k-1]%mod * cmb[c1-k-1][j-k-1]%mod * (j-k+1) % mod);
					//cerr << k << " " << cmb[c1-k-1][j-k-1] << " " << prf[i+1][k] << " " << dp[j-k-1] << " " << (j-k+1) << endl;
				}
			}
		}
		else
		{
			for(int j = 0; j <= c1; j++)
				prf[i][j] = 1ll*prf[i+1][j]*max(0,j-(2*n-i-1-c1))%mod;
		}
		//for(int j = 0; j <= c1; j++) cerr << prf[i][j] << " ";
		//cerr << endl;
	}
	cout << (1ll*prf[1][n] * bpow(bpow(2, n),mod-2) % mod) << endl;
	return 0;
}

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