제출 #852240

#제출 시각아이디문제언어결과실행 시간메모리
852240parsadox2캥거루 (CEOI16_kangaroo)C++14
100 / 100
35 ms16192 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5 , mod = 1e9 + 7;
int n , s , t , dp[N][N] , ans;

int modit(int a)
{
	if(a >= mod)
		return a - mod;
	return a;
}

void solve(int st , int fn)
{
	memset(dp , 0 , sizeof dp);
	dp[0][0] = 1;
	int slm = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		if(i == s)
		{
			for(int j = 1 ; j <= n ; j++)
				dp[i][j] = dp[i - 1][j - st];
			slm++;
			continue;
		}
		if(i == t)
		{
			for(int j = 1 ; j <= n ; j++)
				dp[i][j] = dp[i - 1][j - fn];
			slm++;
			continue;
		}
		for(int j = 1 ; j <= n ; j++)
		{
			dp[i][j] = 1LL * dp[i - 1][j - 1] * max(0 , j - slm) % mod;
			dp[i][j] = modit(dp[i][j] + 1LL * dp[i - 1][j + 1] * j % mod);
		}
	}
	ans = modit(ans + dp[n][1]);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	cin >> n >> s >> t;
	int ty = (n & 1 ? 0 : 1);
	solve(1 , 1 ^ ty);
	solve(0 , 0 ^ ty);
	cout << ans << '\n';
	return 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...