제출 #1294276

#제출 시각아이디문제언어결과실행 시간메모리
1294276Zakir060Kangaroo (CEOI16_kangaroo)C++20
100 / 100
21 ms31756 KiB
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, cs, cf;
    if (!(cin >> N >> cs >> cf)) return 0;

    if (N == 2) {
        cout << 1 << '\n';
        return 0;
    }
    if (cs > cf) swap(cs, cf);
    static long long dp[2001][2001];
    for (int i = 0; i <= N; ++i)
        for (int j = 0; j <= N; ++j)
            dp[i][j] = 0;

    dp[0][0] = 1;

    for (int i = 1; i < cs; ++i) {
        for (int c = 1; c <= i; ++c) {
            dp[i][c] = (dp[i][c] + dp[i-1][c-1] * 1LL * c) % MOD;
        }
        for (int c = 0; c < i; ++c) {
            dp[i][c] = (dp[i][c] + dp[i-1][c+1] * 1LL * c) % MOD;
        }
    }

    if (cs >= 1) {
        for (int c = 0; c <= N; ++c) {
            long long val = dp[cs-1][c];
            if (c > 0) val = (val + dp[cs-1][c-1]) % MOD;
            dp[cs][c] = val;
        }
    }

    for (int i = cs + 1; i < cf; ++i) {
        for (int c = 1; c <= i; ++c) {
            dp[i][c] = (dp[i][c] + dp[i-1][c-1] * 1LL * (c - 1)) % MOD;
        }
        for (int c = 0; c < i; ++c) {
            dp[i][c] = (dp[i][c] + dp[i-1][c+1] * 1LL * c) % MOD;
        }
    }

    for (int c = 0; c <= N; ++c) {
        long long val = dp[cf-1][c];
        if (c > 0) val = (val + dp[cf-1][c-1]) % MOD;
        dp[cf][c] = val;
    }

    for (int i = cf + 1; i <= N; ++i) {
        for (int c = 2; c <= i; ++c) {
            dp[i][c] = (dp[i][c] + dp[i-1][c-1] * 1LL * (c - 2)) % MOD;
        }
        for (int c = 0; c < i; ++c) {
            dp[i][c] = (dp[i][c] + dp[i-1][c+1] * 1LL * c) % MOD;
        }
    }

    cout << dp[N][1] % MOD << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...