Submission #835145

#TimeUsernameProblemLanguageResultExecution timeMemory
835145RaulAndrei01NoM (RMI21_nom)C++14
100 / 100
96 ms109312 KiB
#include <iostream> using namespace std; using ll = long long; const int NMAX = 2002; const int MOD = 1e9 + 7; ll dp[NMAX][NMAX]; ll c[2 * NMAX][2 * NMAX]; ll fact[2 * NMAX], ifact[2 * NMAX]; ll imod(ll x) { ll rez = 1; for (int bit = 0; (1 << bit) <= MOD - 2; bit++) { if ((1 << bit) & (MOD - 2)) { rez = (rez * x) % MOD; } x = (x * x) % MOD; } return rez; } ll aranj(int n, int k) { return (fact[n] * ifact[n - k]) % MOD; } int main() { int n, m; cin >> n >> m; for (int i = 1; i <= 2 * n; i++) { c[i][i] = c[i][0] = 1; for (int j = 1; j < i; j++) { c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD; } } fact[0] = 1; for (int i = 1; i <= 2 * n; i++) { fact[i] = (fact[i - 1] * i) % MOD; } ifact[2 * n] = imod(fact[2 * n]); for (int i = 2 * n - 1; i >= 0; i--) { ifact[i] = (ifact[i + 1] * (1ll * i + 1)) % MOD; } dp[0][0] = 1; for (int i = 1; i <= n; i++) { dp[0][i] = 0; } for (int i = 1; i <= m; i++) { int ni = 2 * n / m + ((2 * n) % m >= i); for (int j = 0; j <= n; j++) { // calc dp[i][j] for (int k = 0; k <= min(ni / 2, j); k++) { dp[i][j] += ((dp[i - 1][j - k] * c[ni][k]) % MOD) * aranj(ni-k , k) % MOD; if (dp[i][j] >= MOD) dp[i][j] -= MOD; } // cout << i << ' ' << j << ' ' << dp[i][j] << '\n'; } } ll bad = 0; ll p2 = 1; for (int i = 1; i <= n; i++) { p2 <<= 1; if (p2 >= MOD) p2 -= MOD; if (i % 2 == 0) { bad -= ((c[n][i] * fact[2 * n - 2 * i] % MOD) * dp[m][i]) % MOD * (fact[i] % MOD) % MOD; if (bad < 0) bad += MOD; } else { bad += ((c[n][i] * fact[2 * n - 2 * i] % MOD) * dp[m][i]) % MOD * (fact[i] % MOD) % MOD; if (bad >= MOD) bad -= MOD; } } ll ans = fact[2 * n]; ans -= bad; if (ans < 0) ans += MOD; cout << ans << '\n'; }
#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...