Submission #30838

#	Time	Username	Problem	Language	Result	Execution time	Memory
30838		szawinis	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	39 ms	17820 KiB

kangaroo

#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; i++) for(int j = 0; j <= i; j++) {
		if(i+1 == n) {
			add(dp[i+1][j], dp[i][j]);
			continue;
		}
		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][0];
}

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