Submission #527620

#	Time	Username	Problem	Language	Result	Execution time	Memory
527620		FireGhost1301	Kangaroo (CEOI16_kangaroo)	C++11	100 / 100	36 ms	14084 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
void add(int &x, int y) {
    x += y;
    while (x >= MOD) x -= MOD;
    while (x < 0) x += MOD;
}

int mul(int x, int y) {
    return (x * 1LL * y) % MOD;
}

const int N = 2e3 + 3;
int n, s, t;
int f[N][N];

void solve() {
    cin >> n >> s >> t;

    f[1][1] = 1;

    for (int i = 1; i < n; ++i) {
        for (int j = 1; j <= i; ++j) if (f[i][j]) {
            if (i + 1 == s || i + 1 == t) {
                add(f[i + 1][j], f[i][j]);
                add(f[i + 1][j + 1], f[i][j]);
            }
            else {
                int x = (i >= s) + (i >= t);
                add(f[i + 1][j + 1], mul(f[i][j], j - x + 1));
                add(f[i + 1][j - 1], mul(f[i][j], j - 1));
            }
        }
    }

    cout << f[n][1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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