Submission #503704

#TimeUsernameProblemLanguageResultExecution timeMemory
503704StickfishNoM (RMI21_nom)C++17
0 / 100
2 ms332 KiB
#include <iostream> using namespace std; using ll = long long; const ll MOD = 1000000007; const ll MAXN = 2077; ll pw(ll a, ll m) { if (!m) return 1; a %= MOD; if (m % 2) return a * pw(a, m - 1) % MOD; return pw(a * a, m / 2); } ll fact[MAXN * 2]; ll rfact[MAXN * 2]; ll choose(ll n, ll k) { if (n < 0 || k < 0 || k > n) return 0; return (fact[n] * rfact[k] % MOD) * rfact[n - k] % MOD; } ll dp[MAXN][MAXN]; signed main() { fact[0] = rfact[0] = 1; for (int i = 1; i < MAXN * 2; ++i) { fact[i] = (fact[i - 1] * i) % MOD; rfact[i] = pw(fact[i], MOD - 2); } int n, m; cin >> n >> m; if (m == 1) { cout << 0 << endl; return 0; } int sz = 2 * n / m; int szinc = 2 * n % m; int smsz = sz + int(0 < szinc); dp[0][0] = choose(n, smsz); //cout << dp[0][0] << endl; for (int i = 1; i < m; ++i) { int szi = sz + int(i < szinc); for (int c = 0; c <= n; ++c) { for (int cp = 0; cp <= c; ++cp) { ll cnt1 = smsz - cp * 2; ll cnt0 = n - cp - cnt1; //if (cnt1 < 0 || cnt0 < 0) //continue; dp[i][c] += (dp[i - 1][cp] * choose(cnt1, c - cp) % MOD) * choose(cnt0, szi - (c - cp)); dp[i][c] %= MOD; } //cout << dp[i][c] << ' '; } smsz += szi; //cout << endl; } cout << dp[m - 1][n] * pw(2, n) % MOD << endl; }
#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...