Submission #763623

#	Time	Username	Problem	Language	Result	Execution time	Memory
763623		amirhoseinfar1385	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	1395 ms	6060 KiB

ruins3

#include<bits/stdc++.h>
using namespace std;
const int maxn=605,tmaxn=1205;
int mod=1e9+7;
long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}
int fact[tmaxn],revfact[tmaxn],magemishe[tmaxn],res[tmaxn][tmaxn],dp[tmaxn],n;
int vas[tmaxn];
int ww(int a){
	if(a>=mod){
		a-=mod;
	}
	return a;
}

void aval(){
	fact[0]=1;
	for(int i=1;i<tmaxn;i++){
		fact[i]=1ll*fact[i-1]*i%mod;
	}
	revfact[tmaxn-1]=mypow(fact[tmaxn-1],mod-2);
	for(int i=tmaxn-2;i>=0;i--){
		revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
	}
}

int c(int i,int j){
	if(i<0||j<0||j>i){
		return 0;
	}
	int ret=1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	cin>>n;
	for(int i=0;i<n;i++){
		int d;
		cin>>d;
		vas[d]=1;
	}
	dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			dp[i]+=1ll*c(i-1,j-1)*(i-j+2)%mod*dp[i-j]%mod*dp[j-1]%mod;
			dp[i]=ww(dp[i]);
		}
	}
	res[n*2+1][0]=1;
	int oomade=0,naumade=0;
	for(int i=n*2;i>=1;i--){
		if(vas[i]){
			for(int j=0;j<=oomade+1;j++){
				res[i][j]=res[i+1][j];
				for(int h=1;h<=j;h++){
					res[i][j]+=1ll*res[i+1][h-1]*dp[j-h]%mod*c(oomade-h+1,j-h)%mod*(j-h+2)%mod;
					res[i][j]=ww(res[i][j]);
				}
			}
			oomade++;
		}
		else{
			for(int j=0;j<=oomade;j++){
				res[i][j]=1ll*res[i+1][j]*max(j-naumade,0)%mod;
			}
			naumade++;
		}
	}
	int mainres=1ll*res[1][n]*mypow(mypow(2,n),mod-2)%mod;
	cout<<mainres<<"\n";
}

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