diff options
| -rw-r--r-- | 21/dec/hilo.cpp | 35 |
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; +} |