Submission #963017

#	Time	Username	Problem	Language	Result	Execution time	Memory
963017		Ghetto	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	37 ms	31732 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 2e3 + 5;
const lint MOD = 1e9 + 7;

int n;
int s, f;

lint mod(lint x) {
    return x % MOD;
}

lint dp[MAX_N][MAX_N];
void do_dp() {
    dp[1][1] = 1;
    for (int i = 1; i < n; i++) {
        for (int c = 1; c <= n; c++) {
            if ((i + 1) == s || (i + 1) == f) {
                dp[i + 1][c + 1] = mod(dp[i + 1][c + 1] + dp[i][c]);
                dp[i + 1][c] = mod(dp[i + 1][c] + dp[i][c]);
                continue;
            }

            lint mult = c + 1;
            mult -= (bool) (i + 1 > s);
            mult -= (bool) (i + 1 > f);
            
            dp[i + 1][c + 1] = mod(dp[i + 1][c + 1] + mod(dp[i][c] * mult));
            dp[i + 1][c - 1] = mod(dp[i + 1][c - 1] + mod(dp[i][c] * (c - 1)));
        }
    }
}

int main() {
    // freopen("kangaroo.in", "r", stdin);

    cin >> n >> s >> f;
    if (s > f) swap(s, f);

    do_dp();
    cout << dp[n][1] << '\n';

    // for (int i = 1; i <= n; i++) 
    //     for (int c = 1; c <= n; c++)
    //         cout << i << " " << c << ": " << dp[i][c] << endl;
    
}

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