Submission #30839

#TimeUsernameProblemLanguageResultExecution timeMemory
30839szawinisKangaroo (CEOI16_kangaroo)C++14
100 / 100
43 ms17820 KiB
#include <bits/stdc++.h>
using namespace std;
const long long MOD = (1e9)+7;

inline void add(int& a, int b) { a = (a + b) % MOD; }
inline int mul(int a, int b) { return 1ll * a * b % MOD; }

int n, s, e, dp[2001][2001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> s >> e;
	dp[0][0] = 1;
	for(int i = 0; i < n-1; i++) for(int j = 0; j <= i; j++) {
		if(i+1 == s || i+1 == e) { // automatically decrease j by 1, since s, e not counted
			add(dp[i+1][j], dp[i][j]); // new cc
			if(j) add(dp[i+1][j-1], mul(dp[i][j], j)); // append to start/end of some cc
		} else {
			add(dp[i+1][j+1], dp[i][j]); // new cc
			if(j >= 2) add(dp[i+1][j-1], mul(dp[i][j], j*(j-1))); // join two non-empty cc
			if(i+1 > s && j) add(dp[i+1][j-1], mul(dp[i][j], j)); // append to start's cc
			if(i+1 > e && j) add(dp[i+1][j-1], mul(dp[i][j], j)); // append to end's cc
		}
	}
	cout << dp[n-1][0];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...