Submission #886456

#	Time	Username	Problem	Language	Result	Execution time	Memory
886456		tsumondai	Bi-ing Lottery Treekets (CCO22_day2problem1)	C++14	25 / 25	120 ms	63656 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define Task "problemname"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 4e3 + 5;

const int oo = 1e9, mod = 1e9 + 7;

int n, k, i;
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 - mod % i] * (mod / i + 1) % mod;
		ff[i] = (long long) ff[i - 1] * i % mod;
		gg[i] = (long long) gg[i - 1] * vv[i] % mod;
	}
}

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

int ll[N + 1], rr[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] % mod * dp[r][kr] % mod;
				else {
					y = (long long) y * choose(c, cc[l] - kl) % mod;
					if (c < cc[i])
						y = (long long) y * dp[l][cc[l]] % mod * dp[r][c + kk[i] - cc[l]] % mod;
					else {
						y = (long long) y * (c - cc[l] + kl) % mod;
						y = (long long) y * dp[l][cc[l]] % mod * dp[r][cc[r]] % mod;
					}
				}
				x = (x + y) % mod;
			}
			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) % mod;
					y = (long long) y * choose(c, cc[l] - kl) % mod;
					y = (long long) y * dp[l][cc[l]] % mod * dp[r][cc[r]] % mod;
					x = (x + y) % mod;
				}
			}
		}
		dp[i][c] = x;
	}
}

void process() {
	init();
	scanf("%d%d", &n, &k);
	if (k > n) {
		printf("0\n");
		return;
	}
	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;
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	if (fopen(Task".INP", "r")) {
		freopen(Task".INP", "r", stdin);
		freopen(Task".OUT", "w", stdout);
	}
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

// dont stop

Compilation message (stderr)

Main.cpp: In function 'void process()':
Main.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%d", &i);
      |   ~~~~~^~~~~~~~~~
Main.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d%d", &ll[i], &rr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:106:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   freopen(Task".INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:107:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   freopen(Task".OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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