제출 #610403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
610403		Arnch	캥거루 (CEOI16_kangaroo)	C++17	0 / 100	256 ms	213448 KiB

kangaroo

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 2e3 + 10, mod = 1e9 + 7;

ll dp[N][N][2][2]; // dp[i][j][t][k] -> left size = i, right size = j, direction of first step = t, destination = k;
// 0 -> left, 1 -> right;
ll ps_l[N][N][2][2];
ll ps_r[N][N][2][2];
ll fac[N], rfac[N];

ll poww(ll x, int y) {
	ll res = 1;
	for(; y; y /= 2, x = x * x % mod)
		if(y & 1) 
			res *= x, res %= mod;
	return res;
}

void pre() {
	fac[0] = 1;
	for(int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
	rfac[N - 1] = poww(fac[N - 1], mod - 2);
	for(int i = N - 2; i >= 0; i--) rfac[i] = rfac[i + 1] * (i + 1) % mod;
}

ll choose(ll x, ll y) {
	if(x < y) return 0;
	if(x == y) return 1;
	return fac[x] * rfac[y] % mod * rfac[x - y] % mod;
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	pre();

	dp[0][0][0][1] = 1;
	dp[0][0][1][0] = 1;
	
	ps_l[0][1][0][1] = 1;
	ps_l[0][1][1][0] = 1;

	ps_r[0][1][0][1] = 1;
	ps_r[0][1][1][0] = 1;

	for(int len = 2; len < N; len++) {
		for(int l = 0; l < len; l++) {
			int r = len - l - 1;

			if(l > 0) {
				dp[l][r][0][0] = ps_l[l - 1][len - 1][1][0];
				dp[l][r][0][1] = ps_l[l - 1][len - 1][1][1];
			}

			if(r > 0) {
				dp[l][r][1][0] = ps_r[r - 1][len - 1][0][0];
				dp[l][r][1][1] = ps_r[r - 1][len - 1][0][1];
			}

			for(int t = 0; t < 2; t++)
				for(int k = 0; k < 2; k++) {
					ps_l[l][len][t][k] += dp[l][r][t][k];
					if(l > 0) ps_l[l][len][t][k] += ps_l[l - 1][len][t][k];
					ps_l[l][len][t][k] %= mod;

					ps_r[r][len][t][k] += dp[l][r][t][k];
					if(r > 0) ps_r[r][len][t][k] += ps_r[r - 1][len][t][k];
					ps_r[r][len][t][k] %= mod;
				}
		}
	}

	int n, s, e; cin >>n >>s >>e;
	if(s > e) swap(s, e);

	if(s == 1) {
		ll ans = dp[e - 1][n - e][0][0] + dp[e - 1][n - e][1][0];
		ans %= mod;
		cout<<ans;
		return 0;
	}
	if(s == n) {
		ll ans = dp[e - 1][n - e][0][1] + dp[e - 1][n - e][1][1];
		ans %= mod;
		cout<<ans;
		return 0;
	}
	if(e == 1) {
		ll ans = dp[s - 1][n - s][0][0] + dp[s - 1][n - s][1][0];
		ans %= mod;
		cout<<ans;
		return 0;
	}
	if(e == n) {
		ll ans = dp[s - 1][n - s][0][1] + dp[s - 1][n - s][1][1];
		ans %= mod;
		cout<<ans;
		return 0;
	}

	ll ans = 0;
	for(int len1 = 0; len1 <= s - 2; len1++) {
		ll cnt1 = choose(s - 2, len1);
		for(int len2 = 0; len2 <= e - s - 1; len2++) {
			ll cnt2 = choose(e - s - 1, len2);
			for(int len3 = 0; len3 <= n - e - 1; len3++) {
				ll cnt3 = choose(n - e - 1, len3);

				ll val = cnt1 * cnt2 % mod * cnt3 % mod;
				val *= (dp[len1 + 1][len2 + len3 + 1][0][0] + dp[len1 + 1][len2 + len3 + 1][1][0]) % mod;
				val %= mod;
				val *= (dp[(s - 1 - len1) + (e - s - 1 - len2)][n - e - 1 - len3][0][0] + dp[(s - 1 - len1) + (e - s - 1 - len2)][n - e - 1 - len3][1][0]);
				val %= mod;

				ans += val, ans %= mod;

				val = cnt1 * cnt2 % mod * cnt3 % mod;
				val *= (dp[len1 + 1][len2 + len3 + 1][0][1] + dp[len1 + 1][len2 + len3 + 1][1][1]) % mod;
				val %= mod;
				val *= (dp[(s - 2 - len1) + (e - s - 1 - len2)][n - e - len3][0][1] + dp[(s - 2 - len1) + (e - s - 1 - len2)][n - e - len3][1][1]);
				val %= mod;
			
				ans += val, ans %= mod;
			}
		}
	}
	
	cout<<ans;


    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49