Submission #1258604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258604		biank	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	30 ms	14152 KiB

kangaroo

#include <bits/stdc++.h>

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

using namespace std;

using vi = vector<int>;

const int MAX_N = 2005;
const int MOD = 1000000007;

int dp[MAX_N][MAX_N];

void add(int &x, int v) {
    x += v;
    if (x >= MOD) x -= MOD;
}

int mul(int a, int b) {
    return int(1LL * a * b % MOD);
}

int main() {
    
    int n, s, t;
    cin >> n >> s >> t;
    --s, --t;
    if (s > t) swap(s, t);
    dp[0][0] = 1;
    forn(i, n) forn(g, n) if (dp[i][g]) {
        if (i < s) {
            if (g > 0) add(dp[i + 1][g - 1], mul(dp[i][g], mul(g, g - 1)));
        } else if (i == s) {
            add(dp[i + 1][g], mul(dp[i][g], g));
        } else if (i < t) {
            if (g > 0) add(dp[i + 1][g - 1], mul(dp[i][g], mul(g - 1, g - 1)));
        } else if (i == t) {
            add(dp[i + 1][g], mul(dp[i][g], g - (i < n - 1)));
        } else {
            if (g > 1) add(dp[i + 1][g - 1], mul(dp[i][g], mul(g - 2, g - 1) + (i == n - 1 && g == 2)));
        }
        add(dp[i + 1][g + 1], dp[i][g]);
    }
    cout << dp[n][1] << '\n';
    
    return 0;
}    

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49