Submission #498651

#	Time	Username	Problem	Language	Result	Execution time	Memory
498651		model_code	NoM (RMI21_nom)	C++17	52 / 100	1078 ms	66016 KiB

Main

// nom_naive_fast_popovici.cpp	
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
 
/*
     Time       O(M * N ^ 2)
     Memory     O(M * N + N * N)
*/
 
 
constexpr int MOD = (int)1e9 + 7;
constexpr int MAXN = 3000;
constexpr int MAXM = 3000;
 
int dp[2][MAXN + 1][2 * MAXN + 1];
short visited[2][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 & 1][N][0] = 1;
    visited[M & 1][N][0] = M + 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++) {
                if (dp[rem & 1][pairs][others] == 0 || visited[rem & 1][pairs][others] != rem + 1)
                    continue;
 
                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 & 1][pairs][others]) % MOD;
 
                    short& last_visited = visited[1 - rem & 1][pairs - p][others + p - (need - p)];
                    int& dp_value = dp[1 - rem & 1][pairs - p][others + p - (need - p)];
                    if (last_visited != rem) {
                        last_visited = rem;
                        dp_value = 0;
                    }
 
                    add(dp_value, 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;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:82:53: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   82 |                     short& last_visited = visited[1 - rem & 1][pairs - p][others + p - (need - p)];
      |                                                   ~~^~~~~
Main.cpp:83:42: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   83 |                     int& dp_value = dp[1 - rem & 1][pairs - p][others + p - (need - p)];
      |                                        ~~^~~~~

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