Submission #498650

#	Time	Username	Problem	Language	Result	Execution time	Memory
498650		model_code	NoM (RMI21_nom)	C++17	9 / 100	1076 ms	204 KiB

Main

// nom_back_popovici.cpp
#include <iostream>
#include <fstream>
 
constexpr int MOD = (int)1e9 + 7;
constexpr int MAXN = 100;
constexpr int MAXM = 100;
 
int where[MAXN + 1];
int freq[MAXN + 1];
int array[2 * MAXN + 1];
int answer = 0;
 
void backtracking(int pos, int N, int M, int current) {
    if (pos == 2 * N) {
        answer += current;
        if (answer >= MOD) {
            answer -= MOD;
        }
 
        // for (int i = 0; i < 2 * N; i++) {
        //     std::cerr << array[i] << " ";
        // }
        // std::cerr << "\n";
 
    } else {
        for (int i = 1; i <= N; i++) {
            if (freq[i] == 0)
                continue;
 
            if (where[i] == -1 || (pos - where[i]) % M != 0) {
                freq[i]--;
                if (freq[i] == 1) {
                    where[i] = pos;
                }
 
                array[pos] = i;
 
                backtracking(pos + 1, N, M, (1LL * current * (freq[i] + 1)) % MOD);
 
                freq[i]++;
                if (freq[i] == 2) {
                    where[i] = -1;
                }
            }
        }
    }
}
 
 
int main() {
    std::istream& fin = std::cin;
    std::ostream& fout = std::cout;
 
    int N, M;
    fin >> N >> M;
 
    std::fill(freq + 1, freq + N + 1, 2);
    std::fill(where + 1, where + N + 1, -1);
    backtracking(0, N, M, 1);
 
    fout << answer << "\n";
 
    return 0;
}

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