Submission #649209

#TimeUsernameProblemLanguageResultExecution timeMemory
649209boris_mihovNoM (RMI21_nom)C++17
21 / 100
548 ms5460 KiB
#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]; int dp[2][MAXN][MAXN]; 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; } } dp[0][0][0] = 1; for (int i = 1 ; i <= m ; ++i) { int len = (2*n - i + 1) / m + (i != 1); for (int zeros = 0 ; zeros <= n ; ++zeros) { for (int ones = 0 ; ones <= n ; ++ones) { for (int addOnes = std::max(0, len - ones) ; addOnes <= std::min(len, zeros) ; ++addOnes) { dp[i&1][zeros][ones] += (((((1LL * dp[!(i&1)][zeros - addOnes][ones + 2*addOnes - len] * comb[len][addOnes]) % MOD) * var[zeros][addOnes]) % MOD) * var[ones][len - addOnes]) % MOD; if (dp[i&1][zeros][ones] >= MOD) dp[i&1][zeros][ones] -= MOD; } } } } int ans = dp[m&1][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...