Submission #227662

#	Time	Username	Problem	Language	Result	Execution time	Memory
227662		imsifile	Ruins 3 (JOI20_ruins3)	C++98	100 / 100	913 ms	3768 KiB

ruins3

#include<stdio.h>

typedef long long lld;
const lld mod=1000000007;

int N, chk[1212], pos[666], neg[666], xs[666];
lld dy[666][666], pw[1212], fac[1212], rfac[1212], rgop[1212], all[666], sums[666];

int cc[666], ba[666], tmp[666], rcn[666];

lld rev(lld a){
	lld g=1;
	for(int r=mod-2; r; r>>=1){
		if(r&1) g=g*a%mod;
		a=a*a%mod;
	}
	return g;
}

lld perm(lld a, lld b){
	if(a<b) return 0;
	return fac[a]*rfac[a-b]%mod;
}

int main(){
	scanf("%d", &N);
	for(int i=1; i<=2*N; i++) chk[i]=1;
	pw[0]=fac[0]=rfac[0]=1;
	for(int i=1; i<=2*N; i++){
		pw[i]=pw[i-1]*((mod+1)/2)%mod;
		fac[i]=fac[i-1]*i%mod;
		rfac[i]=rev(fac[i]);
		rgop[i]=rev(4*i-2);
	}
	for(int i=1; i<=N; i++){
		if(i==1) all[i]=1;
		else all[i]=fac[2*i]*pw[i]%mod*rgop[i]%mod*rfac[i]%mod*rfac[i]%mod;
	}

	for(int i=0; i<N; i++){
		scanf("%d", &neg[i]);
		chk[neg[i]]=-1;
	}
	for(int i=1, pcn=0; i<=2*N; i++){
		if(chk[i]>0) pos[pcn++]=i;
		chk[i]+=chk[i-1];
		if(chk[i]<0){ puts("0"); return 0; }
	}
	xs[N]=N;
	for(int i=0; i<N; i++) xs[i]=(neg[i]-1+chk[neg[i]-1])/2;

	for(int i=N; i>=0; i--){
		for(int k=i+1; k<=N; k++) sums[k]=0;
		for(int j=i; j>=0; j--){
			for(int k=i+1; k<=N; k++){
				sums[k]+=dy[k][j]*all[k-i]%mod*perm(xs[j]-i,k-i)%mod*rfac[i-j]%mod;
				sums[k]%=mod;
			}
			if(i==N && j==N) dy[i][j]=1;
			else if(i==xs[j]) dy[i][j]=dy[i][j+1]*chk[neg[j]-1]%mod;
			else if(i>xs[j]) dy[i][j]=0;
			else {
				for(int k=i+1; k<=N; k++) dy[i][j]+=sums[k]*fac[i-j]%mod;
				dy[i][j]%=mod;
			}
			for(int k=i+1; k<=N; k++){
				sums[k]+=dy[k][j]*all[k-i]%mod*(mod-perm(xs[j-1]-i,k-i))%mod*rfac[i-j]%mod;
				sums[k]%=mod;
			}
		}
	}
	printf("%lld\n", dy[0][0]);
	return 0;
}

Compilation message (stderr)

ruins3.cpp: In function 'int main()':
ruins3.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
ruins3.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &neg[i]);
   ~~~~~^~~~~~~~~~~~~~~

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