Submission #1115752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115752		bleahbleah	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	137 ms	63368 KiB

kangaroo

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
// #define int ll

#define sz(x) ((int)(x).size())

const int nmax = 2e3 + 5;
const int mod = 1e9 + 7;
struct Mint {
	int val;
	Mint(ll x = 0): val((x % mod + mod) % mod) {;}
	Mint operator +(const Mint& x) const { return Mint(val + x.val); }
	Mint operator -(const Mint& x) const { return Mint(val - x.val); }
	Mint operator *(const Mint& x) const { return Mint((ll)val * x.val); }
	Mint operator +=(const Mint& x) { return *this = Mint(val + x.val); }
	Mint operator -=(const Mint& x) { return *this = Mint(val - x.val); }
	Mint operator *=(const Mint& x) { return *this = Mint((ll)val * x.val); }
	Mint operator ^(int b) const {
		Mint accum = 1, a = *this;
		while(b) {
			accum = (b & 1? accum * a : accum);
			a *= a;
			b >>= 1;
		}
		return accum;
	}
	Mint operator /(const Mint& x) { return Mint((ll)val * (x ^ (mod - 2)).val); }
	Mint operator /=(const Mint& x) { return *this = Mint((ll)val * (x ^ (mod - 2)).val); }
};

Mint dp[nmax][nmax][2][2];

signed main() {
	int N, S, T;
	cin >> N >> S >> T;
	
	vector<int> initial(3); 
	iota(all(initial), 1);
	do {
		if(S <= 3 && initial[0] != S) continue;
		if(T <= 3 && initial.back() != T) continue;
		// for(auto x : initial) cerr << x << ' ';
		// cerr << '\n';
		dp[3][(initial[1] > initial[0]) && (initial[2] < initial[1])][initial[1] > initial[0]][initial[2] > initial[1]] += 1;
	} while(next_permutation(all(initial)));
	
	for(int len = 3; len <= N; len++) {
		int stanga = (len + 1 <= S && len + 1 != T), dreapta = (len + 1 <= T && len + 1 != S), inside = (len + 1 != T && len + 1 != S);
		for(int stand = 0; stand <= len - 2; stand++) {
			for(int lval = 0; lval < 2; lval++) {
				for(int rval = 0; rval < 2; rval++) {
					int eq = (len - 2) - (lval == rval? stand * 2 : (lval == 1? stand * 2 - 1 : stand * 2 + 1));
					if(eq < 0) continue;
					
					if(inside) {
						if(lval == 0) // append 1 la inceput (deci 10 nou si restul la fel) (prin 0, i.e. pui pe a doua pozitie)
							dp[len + 1][stand + 1][1][rval] += dp[len][stand][0][rval];
						if(lval == 1); // asta e de inside, nu se poate intampla nimic ce nu e legat de standard/equaluri
						if(rval == 0); // aceeasi poveste, incat insereaza inauntru (deci e legat de stand/eq)
						if(rval == 1) // a doua pozitie, devine 10
							dp[len + 1][stand + 1][lval][0] += dp[len][stand][lval][1];
						// stand devine eq (in doua moduri)
						dp[len + 1][stand][lval][rval] += dp[len][stand][lval][rval] * stand * 2;
						// equal devine stand
						dp[len + 1][stand + 1][lval][rval] += dp[len][stand][lval][rval] * eq;
					}
					if(stanga) {
						dp[len + 1][stand][0][rval] += dp[len][stand][lval][rval];
					}
					if(dreapta) {
						dp[len + 1][stand][lval][1] += dp[len][stand][lval][rval];
					}
				}
			}
		}
	}
	
	Mint sum = 0;
	
	for(int len = N; len <= N; len++) {
		for(int stand = 0; stand <= N; stand++) {
			for(int lval = 0; lval < 2; lval++) {
				for(int rval = 0; rval < 2; rval++) {
					int eq = (len - 2) - (lval == rval? stand * 2 : (lval == 1? stand * 2 - 1 : stand * 2 + 1));
					if(eq == 0)
						cerr << len << ' ' << stand << ' ' << lval << ' ' << rval << '\n',
						sum += dp[len][stand][lval][rval];
				}
			}
		}
	}
	
	cout << sum.val << '\n';
	
	
}

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