제출 #559844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559844		Alexandruabcde	NoM (RMI21_nom)	C++14	100 / 100	88 ms	59468 KiB

Main

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2005;
constexpr int MOD = 1e9 + 7;

int N, M;
int Contor[NMAX];
int CntGrup[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= 2*N; ++ i )
        Contor[i%M + 1] ++;

    for (int i = 1; i <= M; ++ i )
        CntGrup[i] = CntGrup[i-1] + Contor[i];
}

int pow2[2*NMAX];
int fact[2*NMAX];
int Comb[2*NMAX][2*NMAX];

void Precompute () {
    fact[0] = 1;
    pow2[0] = 1;
    for (int i = 1; i <= 2*N; ++ i ) {
        fact[i] = (1LL * fact[i-1] * i) % MOD;
        pow2[i] = (1LL * pow2[i-1] * 2) % MOD;
    }

    Comb[0][0] = 1;
    for (int i = 1; i <= 2*N; ++ i ) {
        Comb[i][0] = Comb[i][i] = 1;

        for (int j = 1; j < i; ++ j )
            Comb[i][j] = (1LL * Comb[i-1][j-1] + 1LL * Comb[i-1][j]) % MOD;
    }
}

int dp[NMAX][NMAX];

void Solve () {
    dp[0][0] = 1;

    for (int grup = 0; grup < M; ++ grup ) {
        int Total = CntGrup[grup];
        for (int j = 0; j <= N && j <= Total; ++ j ) {
            int pairs = (Total - j) / 2;

            if (2 * pairs + j != Total) continue;

            int pos_new_jum = N - pairs - j;
            for (int complete = 0; complete <= j && complete <= Contor[grup+1]; ++ complete ) {
                int new_jum = Contor[grup+1] - complete;

                if (new_jum > pos_new_jum) continue;

                int coef = 1LL * Comb[pos_new_jum][new_jum] * pow2[new_jum] % MOD;
                coef = (1LL * coef * Comb[j][complete]) % MOD;
                coef = (1LL * coef * fact[Contor[grup+1]]) % MOD;

                dp[grup+1][j - complete + new_jum] = (dp[grup+1][j - complete + new_jum] + 1LL * coef * dp[grup][j] % MOD) % MOD;
            }
        }
    }

    cout << dp[M][0] << '\n';
}

int main()
{
    Read();
    Precompute();
    Solve();

    return 0;
}

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