Submission #130566

#	Time	Username	Problem	Language	Result	Execution time	Memory
130566		keko37	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	57 ms	39800 KiB

kangaroo

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;

const int MAXN = 5005;
const int MOD = 1000000007;

int n, x, y;
llint dp[MAXN][MAXN];

int main () {
	cin >> n >> x >> y;
	if (x > y) swap(x, y);
	dp[n+1][0] = 1;
	for (llint i = n; i >= 1; i--) {
		for (llint g = 1; g <= n; g++) {
			 if (y < i) dp[i][g] = (dp[i+1][g-1] + (g+1) * g % MOD * dp[i+1][g+1] % MOD) % MOD;
			 if (i == y) dp[i][g] = (dp[i+1][g-1] + g * dp[i+1][g] % MOD) % MOD;
			 if (x < i && i < y) dp[i][g] = (dp[i+1][g-1] + g * g % MOD * dp[i+1][g+1] % MOD) % MOD;
			 if (i == x) dp[i][g] = (dp[i+1][g-1] + (g-1) * dp[i+1][g] % MOD) % MOD;
			 if (i < x) dp[i][g] = (dp[i+1][g-1] + (g-1) * g % MOD * dp[i+1][g+1] % MOD) % MOD;
		}
	}
	if (x == 1) cout << dp[2][1]; else cout << dp[2][2];
	return 0;
}

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