Add solution to 2021 Dec HILO

1 files changed, 35 insertions, 0 deletions

diff --git a/21/dec/hilo.cpp b/21/dec/hilo.cpp
new file mode 100644
index 0000000..250bf49
--- /dev/null
+++ b/21/dec/hilo.cpp
@@ -0,0 +1,35 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+constexpr int MX = 5005, MOD = 1e9+7;
+
+inline ll pw(ll base, ll exp) {
+	ll res = 1;
+	while (exp) {
+		if (exp & 1) (res *= base) %= MOD;
+		exp >>= 1, (base *= base) %= MOD;
+	}
+	return res;
+}
+
+int inv[MX], pre[2][MX], DP[2][MX][MX];
+
+int main() {
+	cin.tie(0)->sync_with_stdio(0);
+	int N, x; cin >> N >> x;
+	for (int i = 1; i <= N; ++i) inv[i] = pw(i, MOD-2);
+	for (int i = 0; i <= x; ++i) {
+		for (int j = 0; j <= N-x; ++j) {
+			DP[0][i][j] = (ll)(pre[0][i] + pre[1][j]) * inv[i + j] % MOD;
+			DP[1][i][j] = (ll)(pre[0][i] + pre[1][j] + i) * inv[i + j] % MOD;
+			(pre[0][i] += DP[1][i][j]) %= MOD;
+			(pre[1][j] += DP[0][i][j]) %= MOD;
+		}
+	}
+	ll ans = DP[0][x][N-x];
+	for (int i = 1; i <= N; ++i) (ans *= i) %= MOD;
+	cout << ans;
+}