Submission #212445

#	Time	Username	Problem	Language	Result	Execution time	Memory
212445		zscoder	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	850 ms	504 KiB

ruins3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<int> fact;
vector<int> ifact;
vector<int> inv;
vector<int> pow2;
const int MOD = (1e9 + 7);
int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
void radd(int &a, int b)
{
	a=add(a,b); 
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
void rmult(int &a, int b)
{
	a=mult(a,b);
}
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
int choose(int a, int b)
{
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
	return modpow(a,MOD-2);
}
void init(int _n)
{
	fact.clear(); ifact.clear(); inv.clear(); pow2.clear();
	fact.resize(_n+1);
	ifact.resize(_n+1);
	inv.resize(_n+1);
	pow2.resize(_n+1);
	pow2[0]=1;
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=_n;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		fact[i]=mult(fact[i-1],i);
		//ifact[i]=mult(ifact[i-1],inv[i]);
	}
	ifact[_n] = inverse(fact[_n]);
	for(int i=_n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
	for(int i=1;i<=_n;i++)
	{
		inv[i] = mult(fact[i-1],ifact[i]);
	}
}
	
int ways[2222];

int p2(int x)
{
	if(x>=0) return pow2[x];
	else return inverse(pow2[-x]);
}

int ok[2222];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	init(2222);
	int n; cin>>n;
	vi f(n+1);
	vi g(n+1);
	g[0]=f[0]=1;
	//remember, cases like 3,3,4,4 are VALID
	//a[i]>=i, each a[i] appears at most 2 times, count such sequences then shuffle
	//count occurrences of a[i] in reverse order (e.g: 2,1,1,0)
	//we want sum of brk(S)
	for(int i=1;i<=n;i++) 
	{
		f[i]=mult(choose(2*(i+1),i+1),inv[i+2]);
		//cerr<<"F: "<<i<<' '<<f[i]<<'\n';
	}
	for(int i=1;i<=n;i++)
	{
		g[i]=f[i];
		for(int j=1;j<i;j++)
		{
			radd(g[i],MOD-mult(g[j],f[i-j]));
		}
		//cerr<<"G "<<i<<" = "<<g[i]<<'\n';
	}
	for(int i=1;i<=n;i++)
	{
		int ans=0;
		for(int j=1;j<=i;j++)
		{
			radd(ans,mult(j,mult(g[j],f[i-j])));
		}
		ans = mult(ans,fact[i-1]);
		ways[i]=ans;
	}
	for(int i=0;i<n;i++)
	{
		int x; cin>>x; x--;
		ok[x]=1;
	}
	vi old(n+1,0);
	old[0]=1;
	int surv=0;
	int ded=0;
	for(int i=2*n-1;i>=0;i--)
	{
		vi nw(n+1,0);
		if(ok[i])
		{
			for(int j=ded;j<=surv;j++)
			{
				radd(nw[j],old[j]);
				for(int k=j+1;k<=surv+1;k++)
				{
					//most recent one must be chosen, so k-j-1 slots left
					radd(nw[k],mult(old[j],mult(choose(surv-j,k-j-1),ways[k-j])));
				}
			}
		}
		else
		{
			for(int j=ded;j<=surv;j++)
			{
				radd(nw[j],mult(old[j],j-ded));
			}
		}
		if(ok[i]) surv++;
		else ded++;
		old=nw;
	}
	cout<<mult(old[n],p2(-n))<<'\n';
}

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