Submission #871348

#	Time	Username	Problem	Language	Result	Execution time	Memory
871348		TAhmed33	NoM (RMI21_nom)	C++98	100 / 100	92 ms	23924 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int add (int a, int b) {
	a += b; if (a >= MOD) a -= MOD;
	return a;
}
int sub (int a, int b) {
	a -= b; if (a < 0) a += MOD;
	return a;
}
int mul (int a, int b) {
	return (a * 1ll * b) % MOD;
}
int power (int a, int b) {
	if (!b) return 1;
	int u = power(a, b >> 1);
	u = mul(u, u);
	if (b & 1) u = mul(u, a);
	return u;
}
const int MAXN = 5e3 + 25;
int fact[MAXN], inv[MAXN];
void pre () {
	fact[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		fact[i] = mul(i, fact[i - 1]);
	}
	inv[MAXN - 1] = power(fact[MAXN - 1], MOD - 2);
	for (int i = MAXN - 2; i >= 0; i--) {
		inv[i] = mul(i + 1, inv[i + 1]);
	}
}
int nCr (int a, int b) {
	return mul(fact[a], mul(inv[b], inv[a - b]));
}
int nPr (int a, int b) {
	return mul(fact[a], inv[a - b]);
}
int dp[MAXN][MAXN];
int main () {
	pre();
	int n, m;
	cin >> n >> m;
	dp[0][0] = 1;
	int dd[m + 1] = {}; for (int i = 1; i <= 2 * n; i++) dd[i % m]++;
	dd[m] = dd[0];
	for (int i = 0; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int l = 0; l <= min(i, dd[j] / 2); l++) {
				dp[i][j] = add(dp[i][j], mul(dp[i - l][j - 1], mul(nPr(dd[j], 2 * l), nCr(i, l))));
			}
		}
	}
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		int x = dp[i][m];
		x = mul(x, nCr(n, i));
		x = mul(x, fact[2 * n - 2 * i]);
		if ((i & 1)) sum = sub(sum, x);
		else sum = add(sum, x);
	}	
	cout << add(fact[2 * n], sum) << '\n';
}

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