Submission #1325820

#TimeUsernameProblemLanguageResultExecution timeMemory
1325820brendonwNoM (RMI21_nom)C++20
9 / 100
1 ms460 KiB
#include <bits/stdc++.h>

using namespace std;
const long long MOD = 1e9 + 7;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	// idea: spam PIE
	// 2^n * # of ways to assign
	// n! - n * dp[1] + n*(n - 1)*dp[2] - n*(n - 1)*(n - 2)*dp[3] + ...
	// dp[i] = # of ways to assign i pairs s.t. they are all m*k apart
	int n, m;
	cin >> n >> m;
	auto modpow = [&](int a, int b) {
		int ans = 1;
		while (b) {
			if (b & 1) {
				ans = 1ll * a * ans % MOD;
			}
			a = 1ll * a * a % MOD;
			b >>= 1;
		}
		return ans;
	};
	vector<vector<int>> dp(n + 1, vector<int>(1 << (2 * n)));
	dp[0][0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int mask = 0; mask < 1 << (2 * n); ++mask) {
			for (int j = 0; j < 2 * n; ++j) {
				for (int k = j + 1; k < 2 * n; ++k) {
					if ((k - j) % m == 0 || mask >> j & 1 || mask >> k & 1) continue;
					(dp[i + 1][mask ^ (1 << j) ^ (1 << k)] += dp[i][mask]) %= MOD;
				}
			}
		}
	}
	cout << 1ll * dp[n][(1 << (2 * n)) - 1] * modpow(2, n) % MOD;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...