Submission #1004032

#TimeUsernameProblemLanguageResultExecution timeMemory
1004032ef10Kangaroo (CEOI16_kangaroo)C++17
0 / 100
1 ms344 KiB
// Source: https://usaco.guide/general/io

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

#define LL long long
#define MODULE 1000000007

int main() {
	std::ifstream input;
    input.open("kangaroo.in");
    std::ofstream output;
    output.open("kangaroo.out");
	LL N, s, f;
	input >> N >> s >> f;
	LL dp[N+5][N+5]; memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for (LL i = 1; i <= N; i++) {
		for (LL j = 1; j <= i; j++) {
			if (i == s || i == f) {
				if (dp[i-1][j] == 0) continue;
				dp[i][j+1] += dp[i-1][j];
				dp[i][j+1] %= MODULE;
				if (j > 0) {
					dp[i][j] += dp[i-1][j];
					dp[i][j] %= MODULE;
				}
				continue;
			}
			dp[i][j] += dp[i-1][j-1] * (j-(i>s)-(i>f)) % MODULE;
			dp[i][j] %= MODULE;
			dp[i][j] += dp[i-1][j+1]*j % MODULE;
			dp[i][j] %= MODULE;
		}
	}
	output << 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...