Submission #834333

#	Time	Username	Problem	Language	Result	Execution time	Memory
834333		Gondozu	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	26 ms	31700 KiB

kangaroo

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define Gondozu ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector <pair<int, int>>;
using vvi = vector <vector<int>>;

const int OO = 1e9 + 5;
const int N = 2e3 + 5, MOD = 1e9+7;

int n, s, e;
ll dp[N][N];

ll add(ll a, ll b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}
ll mul(ll a, ll b) { return a * b % MOD; }


void TC()
{
    cin >> n >> s >> e;

    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            ll &cur = dp[i][j];
            if(i == s || i == e){
                cur = add(dp[i-1][j], dp[i-1][j-1]);
                continue;
            }

            cur = add(mul(dp[i-1][j+1], j), mul(dp[i-1][j-1], (j - (i>s) - (i>e))));
        }
    }
    cout << dp[n][1];
}

int32_t main() {
    Gondozu
    int t = 1;
//    cin >> t;
    while (t--) {
        TC();
        cout << '\n';
    }
    return 0;
}

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