oj.uz

Submission #940824

# Submission time Handle Problem Language Result Execution time Memory
940824 2024-03-07T17:02:19 Z rainboy 선다형 시험 (TOKI14_multiple) C
100 / 100
 11 ms 504 KB 
#include <stdio.h>

#define N	2000
#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 main() {
	static char s[8];
	static int aa[N], bb[N], dp[N + 1], dq[N + 1];
	int n, x, y, i, k, l, a, c, ans;

	init();
	scanf("%d%d%d", &n, &x, &y);
	for (i = 0; i < n; i++) {
		scanf("%s", s);
		aa[i] = s[0] - 'a';
	}
	for (i = 0; i < n; i++) {
		scanf("%s", s);
		bb[i] = s[0] - 'a';
	}
	dp[0] = dq[0] = 1;
	for (i = 0; i < n; i++) {
		scanf("%s", s);
		c = 0;
		for (a = 0; a < 5; a++)
			if (s[a] != '.')
				c++;
		if (aa[i] == bb[i])
			for (k = n - 1; k >= 0; k--) {
				dp[k + 1] = (dp[k + 1] + dp[k]) % MD;
				dp[k] = (long long) dp[k] * (c - 1) % MD;
			}
		else
			for (k = n - 1; k >= 0; k--) {
				dq[k + 1] = (dq[k + 1] + dq[k]) % MD;
				dq[k] = (long long) dq[k] * (c - 2) % MD;
			}
	}
	ans = 0;
	for (k = 0; k <= n && k <= x && k <= y; k++) {
		l = x + y - k * 2;
		if (l > n)
			continue;
		ans = (ans + (long long) dp[k] * dq[l] % MD * choose(l, x - k)) % MD;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

multiple.c: In function 'main':
multiple.c:29:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d%d%d", &n, &x, &y);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
multiple.c:31:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
multiple.c:35:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
multiple.c:40:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 11 ms 348 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 480 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 11 ms 348 KB Output is correct