From 2fe5303202bddcd64a350bdabcddc11d6426b6e8 Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Fri, 31 Dec 2021 12:12:54 -0600 Subject: Add solution to 2021 Dec HILO --- 21/dec/hilo.cpp | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) create mode 100644 21/dec/hilo.cpp 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 +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +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; +} -- cgit v1.2.3-70-g09d2