Submission #759879

#	Time	Username	Problem	Language	Result	Execution time	Memory
759879		Asamai	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	26 ms	14124 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
// #define     int                   long long

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 2e3 + 5;
const int mod = 1e9 + 7; // 998244353

int n, s, t;
int dp[MAX_N][MAX_N];

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> s >> t;
	dp[1][1] = 1;

	int cnt = 0;

	for (int i = 1; i < n; i++) {
		if (i == s || i == t) cnt++;

		if (i + 1 == s || i + 1 == t) {
			for (int j = 1; j <= i; j++) {
				if (!dp[i][j]) continue;
				// tao ra 1 tplt rieng
				(dp[i + 1][j + 1] += dp[i][j]) %= mod;

				// ghep vao 1 tplt
				(dp[i + 1][j] += dp[i][j]) %= mod;
			}
		}
		else {
			for (int j = 1; j <= i; j++) {
				// tao ra 1 tplt rieng -> j + 1 - cnt vi tri
				if (j + 1 - cnt > 0) {
					(dp[i + 1][j + 1] += 1ll * dp[i][j] * (j + 1 - cnt) % mod) %= mod;
				}

				// ket noi 2 tlpt nao do -> j - 1 vi tri
				(dp[i + 1][j - 1] += 1ll * dp[i][j] * (j - 1) % mod) %= mod;	
			}
		}
	}

	cout << dp[n][1];

	return 0;
}

/*


*/

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