Submission #670366

#	Time	Username	Problem	Language	Result	Execution time	Memory
670366		rainboy	Ruins 3 (JOI20_ruins3)	C11	100 / 100	566 ms	1744 KiB

ruins3

#include <stdio.h>

#define N	600
#define MD	1000000007

int vv[N + 1], ff[N + 1], gg[N + 1], dp[N + 1][N + 1], dq[N + 1];

int choose(int n, int k) {
	return k < 0 || k > n ? 0 : (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}

void init() {
	int i, j;

	ff[0] = gg[0] = 1;
	for (i = 1; i <= N; i++) {
		vv[i] = i == 1 ? 1 : (long long) vv[i - MD % i] * (MD / i + 1) % MD;
		ff[i] = (long long) ff[i - 1] * i % MD;
		gg[i] = (long long) gg[i - 1] * vv[i] % MD;
	}
	dp[0][0] = 1;
	for (i = 0; i <= N; i++)
		for (j = i; j <= N; j++) {
			int x = dp[i][j];

			if (x == 0)
				continue;
			if (i < j)
				dp[i + 2][j] = (dp[i + 2][j] + (long long) x * (i + 1) * (i + 2) / 2) % MD;
			if (i < N && j < N)
				dp[i + 1][j + 1] = (dp[i + 1][j + 1] + (long long) x * (i + 1) * (j + 1)) % MD;
			if (j + 2 <= N)
				dp[i][j + 2] = (dp[i][j + 2] + (long long) x * (j + 1) * (j + 2) / 2) % MD;
		}
	for (j = 0; j <= N; j++) {
		dq[j] = dp[j][j];
		for (i = 1; i < j; i++)
			dq[j] = (dq[j] - (long long) dq[i] * choose(j, i) % MD * choose(j - 1, i - 1) % MD * dp[j - i][j - i]) % MD;
		if (dq[j] < 0)
			dq[j] += MD;
	}
}

int main() {
	static int kk[N], dr[N + 1];
	static char cc[N * 2];
	int n, h, i, j, j_, k, x;

	init();
	scanf("%d", &n);
	for (h = 0; h < n; h++) {
		scanf("%d", &i), i--;
		cc[i] = 1;
	}
	k = 0;
	for (h = 0, i = 0; h < n * 2; h++)
		if (cc[h] == 0)
			k++;
		else
			kk[i++] = k;
	dr[0] = 1;
	for (i = n - 1; i >= 0; i--)
		for (j = n - i; j > 0; j--) {
			x = 0;
			for (j_ = 0; j_ < j; j_++)
				x = (x + (long long) dr[j_] * choose(kk[i] - (n - j), j - j_) % MD * choose(n - i - j_ - 1, j - j_ - 1) % MD * dq[j - j_]) % MD;
			if (j == n)
				printf("%d\n", x);
			else
				dr[j] = (dr[j] + x) % MD;
		}
	return 0;
}

Compilation message (stderr)

ruins3.c: In function 'main':
ruins3.c:50:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
ruins3.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d", &i), i--;
      |   ^~~~~~~~~~~~~~~

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