Submission #1038436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038436		andrei_c1	NoM (RMI21_nom)	C++17	100 / 100	91 ms	60500 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int kMod = 1e9 + 7;

void addSelf(int &x, int y) {
	x += y;
	if(x >= kMod) {
		x -= kMod;
	}
}

int add(int x, int y) {
	addSelf(x, y);
	return x;
}

void multSelf(int &x, int y) {
	x = (ll)x * y % kMod;
}

int mult(int x, int y) {
	multSelf(x, y);
	return x;
}

const int kN = 2000;

int dp[2][2 * kN + 1], comb[2 * kN + 1][2 * kN + 1];

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> cnt(m);
	for(int i = 0; i < 2 * n; i++) {
		cnt[i % m]++;
	}
	comb[0][0] = 1;
	for(int i = 1; i <= 2 * n; i++) {
		comb[i][0] = comb[i][i] = 1;
		for(int j = 1; j < i; j++) {
			comb[i][j] = add(comb[i - 1][j], comb[i - 1][j - 1]);
		}
	}
	int sum = cnt[0];
	dp[0][sum] = 1;
	for(int i = 1; i < m; i++) {
		int fact = 1;
		for(int j = 0; j <= cnt[i]; j++) {
			for(int k = j; k <= sum; k++) {
				int ways = dp[(i - 1) & 1][k];
				multSelf(ways, comb[cnt[i]][j]);
				multSelf(ways, comb[k][j]);
				multSelf(ways, fact);
				addSelf(dp[i & 1][k + cnt[i] - 2 * j], ways);
			}
			multSelf(fact, j + 1);
		}
		for(int k = 0; k <= sum; k++) {
			dp[(i - 1) & 1][k] = 0;
		}
		sum += cnt[i];
	}
	int res = dp[(m - 1) & 1][0];
	for(int i = 1; i <= n; i++) {
		multSelf(res, 2);
		multSelf(res, i);
	}
	cout << res << '\n';
	return 0;
}

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