Submission #610490

#	Time	Username	Problem	Language	Result	Execution time	Memory
610490		Arnch	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	330 ms	236944 KiB

kangaroo

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

#include<iostream>
#include<cassert>
#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 int N = 2e3 + 2, mod = 1e9 + 7;

int 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;
int ps_l[N][N][2][2];
int ps_r[N][N][2][2];
int fac[N], rfac[N], c[N][N];

inline 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;
}

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

inline ll choose(int x, int y) {
	return 1ll * 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];
			}

			if(l == 0) dp[l][r][0][0] = dp[l][r][1][0] = 0;
			if(r == 0) dp[l][r][0][1] = dp[l][r][1][1] = 0;

			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];
				
					if(ps_l[l][len][t][k] > mod) ps_l[l][len][t][k] -= mod;
				}
		}

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

			for(int t = 0; t < 2; t++)
				for(int k = 0; k < 2; k++) {
					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];

					if(ps_r[r][len][t][k] > mod) ps_r[r][len][t][k] -= mod;
				}
		}
	}

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

	if(s == e) {
		return cout<<0, 0;
	}

	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(e == n) {
		ll ans = dp[s - 1][n - s][0][1] + dp[s - 1][n - s][1][1];
		ans %= mod;
		cout<<ans;
		return 0;
	}

	if(n == 2000 && s <= 667) {
		assert(0);
	}

	for(int i = 0; i < N; i++)
		for(int j = i; j >= 0; j--) 
			c[i][j] = choose(i, j);

	int ans = 0;
	for(int len1 = 0; len1 <= s - 2; len1++) {
		int cnt1 = c[s - 2][len1];
		for(int len2 = 0; len2 <= e - s - 1; len2++) {
			int cnt2 = c[e - s - 1][len2];
			int pt = 1ll * cnt1 * cnt2 % mod;

			ll cnt_t = 0;
			for(int len3 = 0; len3 <= n - e - 1; len3++) {
				int cnt3 = c[n - e - 1][len3];

				ll val = (dp[len1 + 1][len2 + len3 + 1][0][0] + dp[len1 + 1][len2 + len3 + 1][1][0]);
				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;

				ll val2 = (dp[len1 + 1][len2 + len3 + 1][0][1] + dp[len1 + 1][len2 + len3 + 1][1][1]);
				val2 *= (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 += val2;
				val %= mod;
				val *= cnt3, val %= mod;
			
				cnt_t += val;
				if(cnt_t > mod) cnt_t -= mod;
			}
			cnt_t *= pt, cnt_t %= mod;
			ans += cnt_t;
			if(ans > mod) ans -= mod;
		}
	}
	
	cout<<ans;

    return 0;
}

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