제출 #1242859

#제출 시각아이디문제언어결과실행 시간메모리
1242859AbdullahIshfaq캥거루 (CEOI16_kangaroo)C++20
100 / 100
68 ms94280 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
void solve(){
	ll n, s, e;
	cin >> n >> s >> e;
	ll dp[n + 1][n + 1][3] = {};
	dp[1][1][(s == 1) | (e == 1)] = 1;
	for(int i = 1; i < n; i ++){
		for(int j = 1; j <= i; j ++){
			if(i + 1 == s or i + 1 == e){
				for(int k = 1; k < 3; k ++){
					dp[i + 1][j][k] += dp[i][j][k - 1];
					dp[i + 1][j][k] %= MOD;
					dp[i + 1][j + 1][k] += dp[i][j][k - 1];
					dp[i + 1][j + 1][k] %= MOD;
				}
			}
			else{
				for(int k = 0; k < 3; k++){
					dp[i + 1][j + 1][k] += dp[i][j][k] * (j + 1 - k);
					dp[i + 1][j + 1][k] %= MOD;
					dp[i + 1][j - 1][k] += dp[i][j][k] * (j - 1);
					dp[i + 1][j - 1][k] %= MOD;
				}
			}
		}
	}
	cout << dp[n][1][2] << '\n';
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll tests = 1;
	// cin >> tests;
	for(ll i = 1; i <= tests; i ++)
		solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...