Submission #605999

#TimeUsernameProblemLanguageResultExecution timeMemory
605999maximath_1Kangaroo (CEOI16_kangaroo)C++11
100 / 100
39 ms31796 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...