Submission #36879

#	Time	Username	Problem	Language	Result	Execution time	Memory
36879		cheater2k	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	39 ms	17880 KiB

kangaroo

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

const int N = 2005;
const int md = 1e9 + 7;

int n, s, t;
int dp[N][N];

void add(int &x, int y) { x += y; while(x >= md) x -= md; if (x < 0) x += md; }

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> s >> t;
	dp[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= i-1; ++j) {
			if (!dp[i-1][j]) continue;
			if (i == s || i == t) {
				if (j) add(dp[i][j], dp[i-1][j]);
				add(dp[i][j+1], dp[i-1][j]);
			}
			else {
				if (j >= 2) add(dp[i][j-1], 1LL * dp[i-1][j] * (j-1) % md);
				int k = j - (i > s) - (i > t) + 1;
				if (k > 0) add(dp[i][j+1], 1LL * dp[i-1][j] * k % md);
			}
		}
	}

	cout << dp[n][1] << endl;
}

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