Submission #503678

#	Time	Username	Problem	Language	Result	Execution time	Memory
503678		atoiz	NoM (RMI21_nom)	C++14	100 / 100	17 ms	344 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MOD = 1000000007;
const int MAXN = 4007;

int N, M;

int add(int a, int b) { return a -= ((a += b) >= MOD ? MOD : 0); }
int sub(int a, int b) { return a += ((a -= b) < 0 ? MOD : 0); }
int mul(int a, int b) { return (int) ((int64_t) a * b % MOD); }
int inv(int a, int m = MOD) { return (a == 1) ? 1 : m - (int) ((int64_t) m * inv(m % a, a) / a); }

int fact[MAXN], ifact[MAXN];
int single[MAXN], dp[MAXN], tmp[MAXN];
int choose(int n, int k) {
	return (n >= k && k >= 0) * mul(fact[n], mul(ifact[k], ifact[n - k]));
}

int main() {
	cin >> N >> M; N *= 2;
	fact[0] = 1; for (int i = 1; i <= N; ++i) fact[i] = mul(fact[i - 1], i);
	ifact[N] = inv(fact[N]); for (int i = N; i >= 1; --i) ifact[i - 1] = mul(ifact[i], i);

	int z = 1;
	dp[0] = 1;

	int t = N / M + 1;
	for (int j = 0; j <= t / 2; ++j) single[j] = mul(fact[t], mul(ifact[j], ifact[t - 2 * j]));
	for (int s = 0; s < N % M; ++s) {
		memset(tmp, 0, sizeof(int) * (z + t / 2));
		for (int i = 0; i < z; ++i) {
			for (int j = 0; j <= t / 2; ++j) {
				tmp[i + j] = add(tmp[i + j], mul(dp[i], single[j]));
			}
		}
		memcpy(dp, tmp, sizeof(int) * (z + t / 2));
		z += t / 2;
	}

	--t;
	for (int j = 0; j <= t / 2; ++j) single[j] = mul(fact[t], mul(ifact[j], ifact[t - 2 * j]));
	for (int s = N % M; s < M; ++s) {
		memset(tmp, 0, sizeof(int) * (z + t / 2));
		for (int i = 0; i < z; ++i) {
			for (int j = 0; j <= t / 2; ++j) {
				tmp[i + j] = add(tmp[i + j], mul(dp[i], single[j]));
			}
		}
		memcpy(dp, tmp, sizeof(int) * (z + t / 2));
		z += t / 2;
	}

	int ans = 0;
	for (int i = 0; i < z; ++i) {
		int x = dp[i];
		x = mul(x, fact[N / 2]);
		x = mul(x, ifact[N / 2 - i]);
		x = mul(x, fact[N - i * 2]);
		if (i & 1) ans = sub(ans, x);
		else ans = add(ans, x);
	}
	cout << ans << endl;
}

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