제출 #163689

#제출 시각아이디문제언어결과실행 시간메모리
163689ryansee캥거루 (CEOI16_kangaroo)C++14
100 / 100
168 ms23120 KiB
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?b:gcd(b%a,a); }

#define ll long long int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (2003)
ll n, cs, cf, mod=1e9+7;
ll dp[MAXN][MAXN];
int main()
{
	FAST
	cin>>n>>cs>>cf;
	if(n<=2) {
		cout<<1<<'\n'; return 0;
	}
	if(cs > cf) swap(cs, cf);
	dp[n+1][0]=1;
	DEC(i, n, 1) FOR(grps, 0, n-i+1) {
		if(i > cf) dp[i][grps] = ((grps?dp[i+1][grps-1]:0) + dp[i+1][grps+1] * (grps+1) % mod * grps % mod) % mod;
		else if(i==cf) dp[i][grps] = (dp[i+1][grps] + dp[i+1][grps+1] * (grps+1) % mod) % mod;
		else if(i>cs) dp[i][grps] = ((grps?dp[i+1][grps-1]:0) + dp[i+1][grps+1] * (((grps+1) * grps % mod + (grps+1))%mod) % mod) % mod;
		else if(i==cs) dp[i][grps] = (dp[i+1][grps] + dp[i+1][grps+1] * (grps+1) % mod) % mod;
		else dp[i][grps] = ((grps?dp[i+1][grps-1]:0) + dp[i+1][grps+1] * (((grps+1)*grps%mod+2*(grps+1)%mod)%mod) % mod) % mod;
	}
	cout<<dp[2][0]<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...