Submission #51695

#	Time	Username	Problem	Language	Result	Execution time	Memory
51695		shoemakerjo	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	96 ms	16772 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;
const int mod = 1000000007;
#define ll long long
#define maxn 2010

int dp[maxn][maxn];
int N;
int cs, cf;

int mult(ll a, ll b) {
	return (a*b)%mod;
}

int go(int cur, int groups) {
	if (cur == N+1) {
		if (groups == 1) return 1;
		return 0; //must have 1 group or else we are bad
	}

	if (groups < 0) return 0;
	if (dp[cur][groups] != -1) {
		return dp[cur][groups]; //already processed this value
	}

	//handle cs and cf separately (i think they might be equivalent though)
	//be careful about edges being bound already
	if (cur == cs || cur == cf) {
		//bind me to my correct side (whatever it is)
		int res = 0;
		//option 1 : add me loosely to my edge
		res += go(cur+1, groups+1);
		res %= mod;

		//option 2 : bind me to the guy when you add me on the edge
		if (groups > 0) {
			res += go(cur+1, groups);
		}
		res %= mod;
		return dp[cur][groups] = res;
	}
	else {
		int numedge = 0; //how many edges there are
		if (cur > cs) numedge++;
		if (cur > cf) numedge++; 

		int numopen = groups+1;
		numopen -= numedge; //one less group here

		int res = 0;

		//option 1 : add me loosely (do it in any open spot, will be surrounded by 2 greater than it)
		res += mult(numopen, go(cur+1, groups+1));
		res %= mod;

		//option 2 : bind 2 groups together (will be surrounded by 2 less than it)
		int numbind = numopen;
		numbind -= 2 - numedge;
		if  (groups >= 2) res += mult(numbind, go(cur+1, groups-1));
		res %= mod;

		return dp[cur][groups] = res;

	} //note that binding to just one group is illegal
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> cs >> cf;
	for (int i = 0; i < maxn; i++) {
		fill(dp[i], dp[i]+maxn, -1);
	}

	int ans = go(1, 0);

	

	cout << ans << endl;
	cin >> ans;

}
//given N, cs and cf
// 1 <= cs <= N
// calculate number of ways to go cs to cf if you alternate between left and right
// 2 <= N <= 2000

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