This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// nom_naive_slow_popovici.cpp
#include <iostream>
#include <fstream>
#include <algorithm>
/*
Time O(M * N ^ 3)
Memory O(M * N ^ 2)
*/
constexpr int MOD = (int)1e9 + 7;
constexpr int MAXN = 300;
constexpr int MAXM = 300;
int dp[MAXM + 1][MAXN + 1][2 * MAXN + 1];
int comb[2 * MAXN + 1][2 * MAXN + 1];
int pow2[2 * MAXN + 1], fact[2 * MAXN + 1];
int counter[MAXM];
inline void add(int& x, int y) {
x += y;
if (x >= MOD)
x -= MOD;
}
void prec(int N, int M) {
for (int i = 0; i <= 2 * N; i++) {
comb[i][0] = 1;
for (int j = 1; j <= i; j++) {
add(comb[i][j], comb[i - 1][j]);
add(comb[i][j], comb[i - 1][j - 1]);
}
}
for (int i = 0; i < 2 * N; i++) {
counter[i % M]++;
}
pow2[0] = fact[0] = 1;
for (int i = 1; i <= 2 * N; i++) {
pow2[i] = (2LL * pow2[i - 1]) % MOD;
fact[i] = (1LL * i * fact[i - 1]) % MOD;
}
}
int main() {
std::istream& fin = std::cin;
std::ostream& fout = std::cout;
int N, M;
fin >> N >> M;
prec(N, M);
dp[M][N][0] = 1;
int used = 0;
for (int rem = M; rem > 0; rem--) {
used += counter[rem];
for (int pairs = 0; pairs <= N; pairs++) {
for (int others = 0; others + 2 * pairs <= 2 * N - used; others++) {
int need = counter[rem - 1];
for (int p = std::max(0, need - others); p <= std::min(pairs, need); p++) {
// if (need > p + others || need < p)
// continue;
int current = (1LL * comb[pairs][p] * comb[others][need - p]) % MOD;
// current = (1LL * current * pow2[p]) % MOD;
current = (1LL * current * dp[rem][pairs][others]) % MOD;
add(dp[rem - 1][pairs - p][others + p - (need - p)], current);
}
}
}
}
int answer = (1LL * dp[0][0][0] * pow2[N]) % MOD;
for (int rem = 0; rem < M; rem++) {
answer = (1LL * answer * fact[counter[rem]]) % MOD;
}
fout << answer << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |