Submission #498649

#	Time	Username	Problem	Language	Result	Execution time	Memory
498649		model_code	NoM (RMI21_nom)	C++17	100 / 100	173 ms	63524 KiB

Main

// nom_100_popovici.cpp
#include <iostream>
#include <fstream>
#include <cassert>
 
/*
     Time       O(M * N + N ^ 2)
     Memory     O(M * N + N ^ 2)
*/
 
 
constexpr int MOD = (int)1e9 + 7;
constexpr int MAXN = 3000;
constexpr int MAXM = 3000;
 
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 dp[MAXM + 1][MAXN + 1];
int ways[MAXN + 1];
 
 
int main() {
    std::istream& fin = std::cin;
    std::ostream& fout = std::cout;
 
    int N, M;
    fin >> N >> M;
 
    prec(N, M);
 
    dp[M][0] = 1;
    for (int rem = M; rem > 0; rem--) {
        for (int i = 0; i <= N; i++) {
            if (dp[rem][i] == 0) 
                continue;
 
            for (int j = 0; 2 * j <= counter[rem - 1]; j++) {
                if (i + j > N)
                    assert(0);
 
                int current = (1LL * comb[N - i][j] * comb[counter[rem - 1]][2 * j]) % MOD;
                current = (1LL * current * fact[2 * j]) % MOD;
                current = (1LL * current * dp[rem][i]) % MOD;
                add(dp[rem - 1][i + j], current);
            }
        }
    }
 
    for (int i = N; i >= 0; i--) {
        ways[i] = (1LL * dp[0][i] * fact[2 * N - 2 * i]) % MOD;
        for (int j = i + 1; j <= N; j++) {
            int current = MOD - (1LL * ways[j] * comb[j][i]) % MOD;
            add(ways[i], current);
        }
    }
 
    fout << ways[0] << "\n";
 
    return 0;
}
 
/*
{1}
        dp[rem][i] * coef -> dp[rem - 1][i + j],    coef = C(N - i, j) * A(counter[rem - 1], 2 * j)
{1}
        ways[i] = dp[0][i] * (2 * N - 2 * i)!
{1}
        ways[i] = ways[i] - sum(ways[j] * C(j, i))
*/

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48