Submission #774385

#	Time	Username	Problem	Language	Result	Execution time	Memory
774385		rainboy	Bi-ing Lottery Treekets (CCO22_day2problem1)	C11	25 / 25	151 ms	46504 KiB

Main

#include <stdio.h>

#define N	4000
#define MD	1000000007

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

void init() {
	int i;

	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;
	}
}

int choose(int n, int k) {
	return (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}

int ll[N + 1], rr[N + 1], sz[N + 1], kk[N + 1], sz[N + 1], cc[N + 1], dp[N + 1][N + 1];

void dfs(int i, int d) {
	int l = ll[i], r = rr[i], c, kl, kr, x, y, tmp;

	if (i == 0)
		return;
	dfs(l, 0);
	dfs(r, 1);
	if (d == 1)
		tmp = l, l = r, r = tmp;
	sz[i] = sz[l] + sz[r] + 1, cc[i] = cc[l] + cc[r] + 1 - kk[i];
	for (c = 0; c <= cc[i]; c++) {
		x = 0;
		for (kl = 0; kl <= kk[i]; kl++) {
			kr = kk[i] - kl;
			if (kl <= cc[l] && kr <= cc[r]) {
				y = choose(kk[i], kl);
				if (c <= cc[l] - kl)
					y = (long long) y * dp[l][c + kl] % MD * dp[r][kr] % MD;
				else {
					y = (long long) y * choose(c, cc[l] - kl) % MD;
					if (c < cc[i])
						y = (long long) y * dp[l][cc[l]] % MD * dp[r][c + kk[i] - cc[l]] % MD;
					else {
						y = (long long) y * (c - cc[l] + kl) % MD;
						y = (long long) y * dp[l][cc[l]] % MD * dp[r][cc[r]] % MD;
					}
				}
				x = (x + y) % MD;
			}
			if (c == cc[i]) {
				kr = kk[i] - kl - 1;
				if (kl <= cc[l] && kr <= cc[r]) {
					y = (long long) choose(kk[i], kl) * (kk[i] - kl) % MD;
					y = (long long) y * choose(c, cc[l] - kl) % MD;
					y = (long long) y * dp[l][cc[l]] % MD * dp[r][cc[r]] % MD;
					x = (x + y) % MD;
				}
			}
		}
		dp[i][c] = x;
	}
}

int main() {
	int n, k, i;

	init();
	scanf("%d%d", &n, &k);
	if (k > n) {
		printf("0\n");
		return 0;
	}
	while (k--) {
		scanf("%d", &i);
		kk[i]++;
	}
	for (i = 1; i <= n; i++)
		scanf("%d%d", &ll[i], &rr[i]);
	sz[0] = 0, cc[0] = 0, dp[0][0] = 1;
	dfs(1, 0);
	printf("%d\n", dp[1][0]);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:78:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d", &i);
      |   ^~~~~~~~~~~~~~~
Main.c:82:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d", &ll[i], &rr[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9