제출 #684898

#제출 시각아이디문제언어결과실행 시간메모리
684898ToniB캥거루 (CEOI16_kangaroo)C++17
100 / 100
21 ms14092 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
const int MOD = 1e9 + 7;

int add(int a, int b){ return (a + b >= MOD) ? a + b - MOD : a + b; }
int sub(int a, int b){ return (a - b < 0) ? a - b + MOD : a - b; }
int mul(int a, int b){ return (long long) a * b % MOD; }

int n, s, f, dp[MAXN][MAXN];

int main(){
	cin >> n >> s >> f;
	if(s > f) swap(s, f);
	dp[0][0] = 1;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= i; ++j){
			if(max(s, f) <= i && i < n && j == 1) continue;
			int choose = mul(j, j + 1);
			if(s < i && i < f) choose = sub(choose, j);
			else if(f < i){
				choose = sub(choose, 2 * j);
				if(i == n) choose = 1;
			}
			else if(i == s) choose = j;
			else if(i == f){
				if(i == n) choose = 1;
				else choose = j - 1;
			}

			if(i == s || i == f){
				dp[i][j] = add(dp[i - 1][j - 1], mul(dp[i - 1][j], choose));
			} else {
				dp[i][j] = add(dp[i - 1][j - 1], mul(dp[i - 1][j + 1], choose));
			}
		}
	}
	cout << dp[n][1];
	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...