Submission #376036

#	Time	Username	Problem	Language	Result	Execution time	Memory
376036		patrikpavic2	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	490 ms	11884 KiB

ruins3

#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1205;
const int MOD = 1e9 + 7;

inline int add(int A, int B){
	if(A + B >= MOD)
		return A + B - MOD;
	return A + B;
}

inline int sub(int A, int B){
	if(A - B < 0)
		return A - B + MOD;
	return A - B;
}

inline int mul(int A, int B){
	return (ll)A * B % MOD; 
}

inline int pot(int A, int B){
	int ret = 1, bs = A;
	for(; B ; B >>= 1){
		if(B & 1) ret = mul(ret, bs);
		bs = mul(bs, bs);
	}
	return ret;
}

int C[N], cat[N], ch[N][N], div2 = (MOD + 1) / 2;
int ubac[N], van[N], A[N], n, dp[N][N], fak[N];

void precompute(){
	for(int i = 0;i < N;i++){
		ch[i][0] = 1, ch[i][i] = 1;
		fak[i] = (i ? mul(fak[i - 1], i) : 1);
	}
	for(int i = 0;i < N;i++)
		for(int j = 1;j < i;j++)
			ch[i][j] = add(ch[i - 1][j - 1], ch[i - 1][j]);
	for(int i = 0;2 * i < N;i++)
		cat[i] = mul(pot(i + 1, MOD - 2), ch[2 * i][i]);
	for(int i = 0;2 * i < N;i++){
		for(int j = 0;j < i;j++){
			if((i - j) % 2 == 1){
				int k = (i - j - 1) / 2;
				C[i] = add(C[i], mul(k, mul(mul(cat[k], ch[i - 1][j]), mul(fak[i - 1], pot(div2, 2 * k)))));
				C[i] = add(C[i], mul(j, mul(mul(cat[k], ch[i - 1][j]), mul(fak[i - 1], pot(div2, 2 * k + 1)))));
				C[i] = add(C[i], mul(1, mul(mul(cat[k], ch[i - 1][j]), mul(fak[i - 1], pot(div2, 2 * k)))));
			}
		}
	}
}

int f(int i, int prf){
	if(i == 0) return (prf == n);
	if(dp[i][prf] != -1) return dp[i][prf];
	if(!A[i]){
		dp[i][prf] = mul(f(i - 1, prf), prf - van[i + 1]);
		return dp[i][prf];
	}
	else{
		int ret = f(i - 1, prf);
		for(int prf2 = prf + 1;prf2 <= ubac[i];prf2++){
			if(prf2 != n - 1 || ubac[i] != n)
				ret = add(ret, mul(f(i - 1, prf2), mul(C[prf2 - prf], ch[ubac[i] - prf - 1][prf2 - prf - 1])));
		}
		return dp[i][prf] = ret;
	}
}

int main(){
	memset(dp, -1, sizeof(dp));
	scanf("%d", &n); precompute();
	for(int i = 0;i < n;i++){
		int x; scanf("%d", &x); 
		A[x] = 1;
	}
	for(int i = 2 * n;i >= 1;i--){
		ubac[i] = ubac[i + 1] + A[i];
		van[i] = van[i + 1] + !A[i];
	}
	printf("%d\n", f(2 * n, 0));
	return 0;
}

Compilation message (stderr)

ruins3.cpp: In function 'int main()':
ruins3.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |  scanf("%d", &n); precompute();
      |  ~~~~~^~~~~~~~~~
ruins3.cpp:82:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |   int x; scanf("%d", &x);
      |          ~~~~~^~~~~~~~~~

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