Submission #678834

#	Time	Username	Problem	Language	Result	Execution time	Memory
678834		rainboy	Tents (JOI18_tents)	C11	100 / 100	255 ms	35568 KiB

tents

#include <stdio.h>

#define N	3000
#define M	3000
#define MD	1000000007

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

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;
	}
	for (i = 0; i <= N; i++)
		for (j = 0; j <= M; j++)
			if (i == 0)
				dp[i][j] = j == 0 ? 1 : 0;
			else
				dp[i][j] = (dp[i - 1][j] + (j == 0 ? 0 : (long long) dp[i - 1][j - 1] * j * 2) + (j < 2 ? 0 : (long long) dp[i - 1][j - 2] * j * (j - 1) / 2)) % MD;
}

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

int main() {
	int n, m, i, j, ans;

	init();
	scanf("%d%d", &n, &m);
	ans = 0;
	for (i = 0; i <= n; i++)
		for (j = 0; j <= m; j++)
			ans = (ans + (long long) dp[i][j] * dp[m - j][n - i] % MD * choose(n, i) % MD * choose(m, j) % MD) % MD;
	ans = (ans - 1 + MD) % MD;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52