Submission #1213307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213307		k1r1t0	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++20	100 / 100	3215 ms	1096 KiB

festival2

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 21000;

int n, MOD, dp[2][2][N];

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> MOD;
	dp[0][0][2] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < N; j++) {
			(dp[1][0][2] += dp[0][0][j]);
			(dp[1][1][1] += dp[0][0][j] * j);
			if (j + 2 < N) (dp[1][0][j + 2] += dp[0][1][j]);
			if (j + 1 < N) (dp[1][0][j + 1] += dp[0][0][j] * (2 * (i - 1) - j));
			if (j + 1 < N) (dp[1][1][j + 1] += dp[0][1][j] * (2 * (i - 1) - j));
		}
		for (int j = 0; j < 2; j++)
		for (int k = 0; k < N; k++) {
			dp[0][j][k] = dp[1][j][k] % MOD;
			dp[1][j][k] = 0;
		}
	}
	int ans = 0;
	for (int i = 0; i < 2; i++)
	for (int j = 0; j < N; j++)
		(ans += dp[0][i][j]) %= MOD;
	int all = 1;
	for (int i = 1; i <= n; i++)
		(all *= 2 * (i - 1) + 1) %= MOD;
	cout << (all - ans + MOD) % MOD;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 27 / 27
• Subtask 4: 14 / 14
• Subtask 5: 36 / 36
• Subtask 6: 13 / 13