Submission #607739

#	Time	Username	Problem	Language	Result	Execution time	Memory
607739		Drew_	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	59 ms	17108 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
 
const int mod = 1e9 + 7;
 
template<int MOD = mod>
struct Mint
{
	int val;
 
	Mint(int64_t val_ = 0) : val((int)(val_ % MOD)) { if (val < 0) val += MOD; }
 
	Mint& operator+= (const Mint &rhs) { val += rhs.val; if (val >= MOD) val -= MOD; return *this; }
	Mint& operator-= (const Mint &rhs) { val -= rhs.val; if (val < 0) val += MOD; return *this; }
	Mint& operator*= (const Mint &rhs) { val = (int)(1ll * val * rhs.val % MOD); return *this; }
 
	friend Mint fpow(Mint x, int64_t y)
	{
		Mint res = 1;
		for (; y > 0; y >>= 1, x *= x) if (y & 1)
			res *= x;
		return res;
	}
	friend Mint inverse(Mint x) { return fpow(x, MOD-2); }
	Mint& operator/= (const Mint &rhs) { return *this *= inverse(rhs); }
 
	friend Mint operator+ (Mint a, const Mint &b) { return a += b; }
	friend Mint operator- (Mint a, const Mint &b) { return a -= b; }
	friend Mint operator- (Mint a) { return 0 - a; }
	friend Mint operator* (Mint a, const Mint &b) { return a *= b; }
	friend Mint operator/ (Mint a, const Mint &b) { return a /= b; }
 
	friend bool operator== (const Mint &a, const Mint &b) { return a.val == b.val; }
	friend bool operator!= (const Mint &a, const Mint &b) { return a.val != b.val; }
	friend ostream& operator<< (ostream &os, const Mint &a) { return os << a.val; }
};
 
namespace brute
{
	void solve(int n, int s, int t)
	{
		vector<int> v(n);
		iota(v.begin(), v.end(), 1);
 
		int ctr[69][69] = {};
 
		do
		{
			bool ok = true;
			for (int i = 1; i+1 < n; ++i)
			{
				if (v[i] > v[i-1] == v[i] > v[i+1]);
				else ok = false;
			}
 
			if (ok)
			{
				ctr[v[0]][v.back()]++;
				// if (v[0] == s && v.back() == t)
				// {
				// 	for (int x : v)
				// 		cerr << x << ", ";
				// 	cerr << '\n';
				// }
			}
 
		} while (next_permutation(v.begin(), v.end()));
 
		cerr << ctr[s][t] << '\n';
		// for (int i = 1; i <= n; ++i)
		// 	for (int j = 1; j <= n; ++j)
		// 		cerr << ctr[i][j] << " \n"[j == n];
	}
}
 
const int MAX = 2069;
 
int N, S, T;
Mint<> dp[MAX][MAX]; // dp[index][low points]
 
int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	cin >> N >> S >> T;
 
	// brute :: solve(N, S, T);
 
	dp[0][0] = 1;
	int ctr = 0; // end points
	for (int i = 1; i <= N; ++i)
	{
		if (i == S || i == T)
		{
			if (ctr == 0)
			{
				// act as high end point
				for (int j = 1; j <= N; ++j)
					dp[i][j] += dp[i-1][j];
 
				// act as new low point
				for (int j = 0; j <= N; ++j)
					dp[i][j+1] += dp[i-1][j];
			}
			else
			{
				if (i == N)
				{
					dp[i][1] += dp[i-1][1]; // end point
				}
				else
				{
					// act as high end point
					for (int j = 2; j <= N; ++j)
						dp[i][j] += dp[i-1][j];
 
					// act as new low point
					for (int j = 1; j <= N; ++j)
						dp[i][j+1] += dp[i-1][j];
				}
			}
 
			ctr++;
		}
		else
		{
			// connect two low points
			for (int j = 2; j <= N; ++j)
			{
				// simply merge two middle components
				if (j - ctr >= 2)
				{
					dp[i][j-1] += (j - ctr - 1) * dp[i-1][j];
				}
 
				// merge left or right component
				if (j - ctr >= 1)
				{
					dp[i][j-1] += ctr * dp[i-1][j];
				}
 
				// merge left and right component
				if (j == 2 && i == N)
				{
					dp[i][j-1] += dp[i-1][j];	
				}
			}
 
			// add new low points
			for (int j = ctr; j <= N; ++j)
				dp[i][j+1] += (j+1 - ctr) * dp[i-1][j];
		}
 
		// cerr << "i -> " << i << '\n';
		// for (int j = 1; j <= N; ++j)
		// 	cerr << j << ": " << dp[i][j] << '\n';
		// cerr << "\n\n";
	}
 
	cout << dp[N][1] << '\n';
	return 0;
}

Compilation message (stderr)

kangaroo.cpp: In function 'void brute::solve(int, int, int)':
kangaroo.cpp:52:14: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   52 |     if (v[i] > v[i-1] == v[i] > v[i+1]);

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