제출 #530352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530352		Servus2022	Zapina (COCI20_zapina)	C++14	110 / 110	263 ms	3224 KiB

zapina

#include <bits/stdc++.h>

using namespace std;

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

int N;

int dp_not_Good[NMAX][NMAX];
int dp_Total[NMAX][NMAX];
int Comb[2*NMAX][2*NMAX];

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

    cin >> N;
}

void Precalculare () {
    Comb[0][0] = 1;

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

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

void Solve () {
    dp_not_Good[0][0] = 1;
    dp_Total[0][0] = 1;

    for (int i = 1; i <= N; ++ i ) {
        for (int j = 0; j <= N; ++ j ) {
            for (int cnt = 0; cnt <= j; ++ cnt ) {
                if (cnt == i) continue;

                dp_not_Good[i][j] = (1LL * dp_not_Good[i][j] + 1LL * Comb[j][cnt] * dp_not_Good[i-1][j-cnt]) % MOD;
            }

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

    cout << (dp_Total[N][N] - dp_not_Good[N][N] + MOD) % MOD << '\n';
}

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

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55