Submission #605999

#	Time	Username	Problem	Language	Result	Execution time	Memory
605999		maximath_1	Kangaroo (CEOI16_kangaroo)	C++11	100 / 100	39 ms	31796 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
const ll mod = 1e9 + 7;
int n, s, e;
ll dp[2005][2005];
 
ll solve(int x, int y){
	memset(dp, 0, sizeof(dp));
	dp[n + 1][0] = 1;
	int oc = 0;
	for(int i = n; i >= 1; i --){
		for(int j = 1; j <= n - i + 1; j ++){
			if(i == s) (dp[i][j] += dp[i + 1][j - x]) %= mod;
			else if(i == e) (dp[i][j] += dp[i + 1][j - y]) %= mod;
			else (dp[i][j] += (dp[i + 1][j - 1] * 1ll * (j - oc) + dp[i + 1][j + 1] * 1ll * j) % mod) %= mod;
		}
		if(i == e || i == s) oc ++;
	}
	return dp[1][1];
}
 
int main(){
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n >> s >> e;
	cout << (solve(0, (n + 1) % 2) + solve(1, n % 2)) % mod << endl;
}

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