제출 #1241170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241170		kaiboy	캥거루 (CEOI16_kangaroo)	C++20	100 / 100	18 ms	444 KiB

kangaroo

#include <algorithm>
#include <iostream>

using namespace std;

const int  N = 2000;
const int MD = 1000000007;

int dp0[N], dp1[N], dq0[N], dq1[N];

int main() {
	int n, s, t; cin >> n >> s >> t, s--, t--;
	if (s > t)
		swap(s, t);
	if (!s)
		dp0[1] = 1;
	else if (s == 1)
		dp1[1] = 1;
	else
		dp0[1] = dp1[1] = 1;
	bool has_s = s < 2, has_t = t < 2;
	for (int i = 2; i < n; i++) {
		for (int k = 0; k <= i; k++)
			dq0[k] = dq1[k] = 0;
		if (i != s && i != t) {
			for (int k = 0; k < i; k++) {
				long long x0 = dp0[k], x1 = dp1[k];
				if (x0) {
					if (k % 2 == 0)
						dq0[k] = (dq0[k] + x0 * k) % MD;
					else
						dq0[k] = (dq0[k] + x0 * (k - 1)) % MD;
					if (i - 1 - k > 0)
						dq0[k + 2] = (dq0[k + 2] + x0 * (i - 1 - k)) % MD;
					if (k % 2)
						dq0[k + 1] = (dq0[k + 1] + x0) % MD;
					if (!has_s)
						dq1[k + 1] = (dq1[k + 1] + x0) % MD;
					if (!has_t) {
						if (k % 2 == 0)
							dq0[k + 1] = (dq0[k + 1] + x0) % MD;
						else
							dq0[k] = (dq0[k] + x0) % MD;
					}
				}
				if (x1) {
					if (k % 2 == 0)
						dq1[k] = (dq1[k] + x1 * (k - 2)) % MD;
					else
						dq1[k] = (dq1[k] + x1 * (k - 1)) % MD;
					if (i - 1 - k > 0)
						dq1[k + 2] = (dq1[k + 2] + x1 * (i - 1 - k)) % MD;
					dq0[k + 1] = (dq0[k + 1] + x1) % MD;
					if (k % 2 == 0)
						dq1[k + 1] = (dq1[k + 1] + x1) % MD;
					if (!has_s)
						dq1[k] = (dq1[k] + x1) % MD;
					if (!has_t)
						if (k % 2)
							dq1[k + 1] = (dq1[k + 1] + x1) % MD;
						else
							dq1[k] = (dq1[k] + x1) % MD;
				}
			}
		} else if (i == s) {
			for (int k = 0; k < i; k++) {
				long long x0 = dp0[k], x1 = dp1[k];
				if (x0)
					dq1[k + 1] = (dq1[k + 1] + x0) % MD;
				if (x1)
					dq1[k] = (dq1[k] + x1) % MD;
			}
			has_s = true;
		} else {
			for (int k = 0; k < i; k++) {
				long long x0 = dp0[k], x1 = dp1[k];
				if (x0) {
					if (k % 2 == 0)
						dq0[k + 1] = (dq0[k + 1] + x0) % MD;
					else
						dq0[k] = (dq0[k] + x0) % MD;
				}
				if (x1) {
					if (k % 2)
						dq1[k + 1] = (dq1[k + 1] + x1) % MD;
					else
						dq1[k] = (dq1[k] + x1) % MD;
				}
			}
			has_t = true;
		}
		for (int k = 0; k <= i; k++)
			dp0[k] = dq0[k], dp1[k] = dq1[k];
	}
	cout << (dp0[n - 1] + dp1[n - 1]) % MD << '\n';
	return 0;
}

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