Submission #1038419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038419		andrei_c1	NoM (RMI21_nom)	C++17	100 / 100	294 ms	604 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;
}

int fact(int n) {
	static vector<int> data(1, 1);
	for(int i = data.size(); i <= n; i++) {
		data.emplace_back(mult(data[i - 1], i));
	}
	return data[n];
}

int inv(int n) {
	static vector<int> data(2, 1);
	for(int i = data.size(); i <= n; i++) {
		data.emplace_back(mult(data[kMod % i], kMod - kMod / i));
	}
	return data[n];
}

int ifact(int n) {
	static vector<int> data(2, 1);
	for(int i = data.size(); i <= n; i++) {
		data.emplace_back(mult(data[i - 1], inv(i)));
	}
	return data[n];
}

int comb(int n, int k) {
	if(k > n) return 0;
	return mult(fact(n), mult(ifact(k), ifact(n - k)));
}

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]++;
	}
	int sum = cnt[0];
	vector<int> dp(sum + 1);
	dp[sum] = 1;
	for(int i = 1; i < m; i++) {
		vector<int> ndp(sum + cnt[i] + 1);
		for(int j = 0; j <= cnt[i]; j++) {
			for(int k = j; k <= sum; k++) {
				int ways = dp[k];
				multSelf(ways, comb(cnt[i], j));
				multSelf(ways, comb(k, j));
				multSelf(ways, fact(j));
				addSelf(ndp[k + cnt[i] - 2 * j], ways);
			}
		}
		dp = ndp;
		sum += cnt[i];
	}
	int res = mult(dp[0], fact(n));
	for(int i = 0; i < n; i++) {
		multSelf(res, 2);
	}
	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