제출 #1325836

#제출 시각아이디문제언어결과실행 시간메모리
1325836brendonwNoM (RMI21_nom)C++20
52 / 100
859 ms12280 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;
	};

	// split into multiple "highways" of bad things
	// m highways, choose 2*k from each one
	vector<int> fact(2 * n + 1);
	fact[0] = 1;
	for (int i = 1; i <= 2 * n; ++i) {
		fact[i] = 1ll * fact[i - 1] * i % MOD;
	}
	vector<int> inv(2 * n + 1);
	inv[2 * n] = modpow(fact[2 * n], MOD - 2);
	for (int i = 2 * n - 1; i >= 0; --i) {
		inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
	}
	vector<vector<int>> dp(m + 1, vector<int>(n + 1));
	auto C = [&](int a, int b) {
		return 1ll * (1ll * fact[a] * inv[a - 2 * b]) % MOD * modpow(modpow(2, b), MOD - 2) % MOD;
	};
	dp[0][0] = 1;
	for (int i = 0; i < m; ++i) {
		// number in current highway:
		int cnt = (i < ((2 * n) % m) ? (2 * n) / m + 1 : (2 * n) / m);
		for (int used = 0; used <= n; ++used) {
			for (int j = 0; j <= cnt >> 1; ++j) {
				if (used + j <= n) {
					(dp[i + 1][used + j] += (1ll * (1ll * dp[i][used] * C(cnt, j) % MOD) * inv[j] % MOD)) %= MOD;
				}
			}
		}
	}
	int ans = C(2 * n, n);
	int prod = 1;
	for (int i = 1; i <= n; ++i) {
		prod = 1ll * prod * (n - i + 1) % MOD;
		(ans += 1ll * (1ll * (i & 1 ? -1 : 1) * prod * dp[m][i] % MOD) * C(2 * n - 2 * i, n - i) % MOD) %= MOD;
		if (ans < 0) {
			ans += MOD;
		}
	}
	cout << 1ll * ans * 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...