Submission #796648

#	Time	Username	Problem	Language	Result	Execution time	Memory
796648		rainboy	NoM (RMI21_nom)	C11	100 / 100	48 ms	356 KiB

Main

#include <stdio.h>

#define N	2000
#define MD	1000000007

int pp2[N * 2 + 1], vv[N * 2 + 1], ff[N * 2 + 1], gg[N * 2 + 1];

void init() {
	int i;

	pp2[0] = ff[0] = gg[0] = 1;
	for (i = 1; i <= N * 2; i++) {
		pp2[i] = pp2[i - 1] * 2 % MD;
		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 int dp[N + 1];
	int n, n_, m, r, k1, k2, l, l1, l2, x;

	init();
	scanf("%d%d", &n, &m);
	n_ = n * 2;
	dp[n] = 1;
	for (r = 0; r < m; r++) {
		l = (n * 2 + m - 1 - r) / m;
		for (k2 = 0; k2 * 2 <= n_; k2++) {
			k1 = n_ - k2 * 2, x = dp[k2];
			if (x == 0)
				continue;
			dp[k2] = 0;
			for (l2 = 0; l2 <= l && l2 <= k2; l2++) {
				l1 = l - l2;
				if (l1 >= 0 && l1 <= k1)
					dp[k2 - l2] = (dp[k2 - l2] + (long long) x * choose(k1, l1) % MD * choose(k2, l2) % MD * pp2[l2] % MD * ff[l]) % MD;
			}
		}
		n_ -= l;
	}
	printf("%d\n", dp[0]);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48