Submission #649214

#TimeUsernameProblemLanguageResultExecution timeMemory
649214boris_mihovNoM (RMI21_nom)C++17
100 / 100
260 ms71028 KiB
#include <unordered_map> #include <algorithm> #include <iostream> #include <numeric> #include <vector> #include <set> typedef long long llong; const int MAXN = 2000 + 10; const int MOD = 1e9 + 7; const int INF = 1e9; int n, m; int fact[MAXN]; int var[MAXN][MAXN]; int comb[MAXN][MAXN]; inline llong getKey(int idx, int zeros, int ones) { return 1LL * idx * MAXN * MAXN + zeros * MAXN + ones; } std::unordered_map <llong,int> dp; int f(int idx, int zeros, int ones) { if (idx == 0) { return (zeros == 0 && ones == 0); } llong key = getKey(idx, zeros, ones); if (dp.count(key)) { return dp[key]; } int res = 0; int len = (2*n - idx + 1) / m + (idx != 1); for (int addOnes = std::max(0, len - ones) ; addOnes <= std::min(len, zeros) ; ++addOnes) { res += (((((1LL * f(idx-1, zeros - addOnes, ones + 2*addOnes - len) * comb[len][addOnes]) % MOD) * var[zeros][addOnes]) % MOD) * var[ones][len - addOnes]) % MOD; if (res >= MOD) res -= MOD; } return dp[key] = res; } void solve() { for (int i = 0 ; i <= n ; ++i) { comb[i][0] = 1; } fact[0] = 1; for (int i = 1 ; i <= n ; ++i) { fact[i] = (1LL * fact[i-1] * i) % MOD; } for (int i = 1 ; i <= n ; ++i) { for (int j = 1 ; j <= i ; ++j) { comb[i][j] = comb[i-1][j] + comb[i-1][j-1]; if (comb[i][j] >= MOD) comb[i][j] -= MOD; } } for (int i = 0 ; i <= n ; ++i) { for (int j = 0 ; j <= i ; ++j) { var[i][j] = (1LL * comb[i][j] * fact[j]) % MOD; } } int ans = f(m, n, 0); for (int i = 1 ; i <= n ; ++i) { ans *= 2; ans %= MOD; } std::cout << ans << '\n'; } void read() { std::cin >> n >> m; } void fastIO() { std::ios_base :: sync_with_stdio(0); std::cout.tie(nullptr); std::cin.tie(nullptr); } int main() { fastIO(); read(); solve(); return 0; }
#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...