Submission #36879

#TimeUsernameProblemLanguageResultExecution timeMemory
36879cheater2kKangaroo (CEOI16_kangaroo)C++14
100 / 100
39 ms17880 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...