Submission #545534

#TimeUsernameProblemLanguageResultExecution timeMemory
545534sidonKangaroo (CEOI16_kangaroo)C++17
100 / 100
19 ms312 KiB
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int Z = 2e3+2;
const i64 MOD = 1e9+7;

inline int mul(const i64 &x, const i64 &y) {
	return (x * y) % MOD;
}

inline int add(int x, const int &y) {
	if((x += y) >= MOD) x -= MOD;
	return x;
}

int N, cs, cf, dp[Z] {1}, prv[Z];

int main() {
	cin >> N >> cs >> cf;

	for(int i = 1; i <= N; ++i) {
		copy(dp, dp + Z, prv);
		dp[0] = 0;
		if(i == cs || i == cf) {
			for(int j = 1; j <= N; ++j)
				dp[j] = add(prv[j-1], prv[j]);
		} else {
			for(int j = 1; j <= N; ++j)
				dp[j] = add(mul(prv[j+1], j), mul(prv[j-1], j - (i > cs) - (i > cf)));
		}
	}

	cout << dp[1];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...