Submission #227645

#	Time	Username	Problem	Language	Result	Execution time	Memory
227645		imsifile	Ruins 3 (JOI20_ruins3)	C++98	58 / 100	6067 ms	3496 KiB

ruins3

#include<stdio.h>

typedef long long lld;
const lld mod=1000000007;

int N, chk[1212], pos[666], neg[666];
lld dy[666][666], pw[1212], fac[1212], rfac[1212], rgop[1212], all[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; }
	}
	for(int i=N; i>=0; i--){
		for(int j=i; j>=0; j--){
			if(i==N && j==N) dy[i][j]=1;
			else if(i==N || pos[i]>neg[j]) dy[i][j]=dy[i][j+1]*chk[neg[j]-1]%mod;
			else {
				for(int must=0; must<=i-j; must++){
					int x=chk[neg[j+must]-1]+j+must-i, y=0;
					if(must) y=chk[neg[j+must-1]-1]+j+must-1-i;
					if(x==y) continue;
					for(int k=1; k<=x; k++){
						lld pm=(perm(x,k)-perm(y,k)+mod)*perm(i-j,must)%mod;
						dy[i][j]+=dy[i+k][j+must]*all[k]%mod*pm%mod;
					}
				}
				dy[i][j]%=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: 0 / 42