Submission #796986

#	Time	Username	Problem	Language	Result	Execution time	Memory
796986		GusterGoose27	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	100 / 100	4834 ms	1136 KiB

festival2

#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, MOD;

const int MAXN = 20005;

typedef unsigned long long ull;

inline int get_mod(int a) {
	return a >= MOD ? a-MOD : a;
}

struct FastMod {
	ull b, m;
	FastMod() {}
	FastMod(ull b) : b(b), m(-1ULL / b) {}
	ull reduce(ull a) { // a % b + (0 or b)
		return get_mod(a - (ull)((__uint128_t(m) * a) >> 64) * b);
	}
};

struct mint {
	int a;
	mint(int a) : a(a) {}
	mint() {}
};

FastMod fastmod;

mint dp[MAXN][2];
mint fac[3*MAXN];
mint facinv[3*MAXN];

mint operator+(mint a, mint b) {
	return mint(get_mod(a.a+b.a));
}

mint operator*(mint a, mint b) {
	return mint(fastmod.reduce((ull)a.a*b.a));
}

mint expo(mint a, int b) {
	mint cur(1);
	while (b) {
		if (b & 1) {
			cur = cur*a;
		}
		a = a*a;
		b /= 2;
	}
	return cur;
}

mint inv(mint a) {
	return expo(a, MOD-2);
}

mint choose(int a, int b) {
	return fac[a]*facinv[b]*facinv[a-b];
}

int main() {
	cin >> n >> MOD;
	fastmod = FastMod(MOD);
	fac[0] = facinv[0] = mint(1);
	for (int i = 1; i <= 3*n; i++) {
		fac[i] = mint(i)*fac[i-1];
	}
	facinv[3*n] = inv(fac[3*n]);
	for (int i = 3*n-1; i > 0; i--) {
		facinv[i] = mint(i+1)*facinv[i+1];
	}
	dp[0][0] = dp[0][1] = mint(1);
	// for (int i = 0; i <= n; i++) {
	// 	dp[0][0] = fac[i];
	// 	dp[0][1] = fac[i+1];
	// }
	for (int i = 1; i <= n; i++) {
		for (int a = 0; a <= i-1; a++) {
			for (int t2 = 0; t2 < 2; t2++) {
				if (t2 && a == i-1) continue; // factorial of 
				mint cur = dp[i-a-1-t2][t2]*fac[a+t2]*choose(2*i-a-t2-2, a);
				dp[i][0] = dp[i][0]+cur;
				dp[i][1] = dp[i][1]+cur*(a+1+t2);
			}
		}
	}
	ll oth = 1;
	for (int i = 2*n-1; i > 0; i -= 2) {
		oth = fastmod.reduce(oth*i);
	}
	cout << fastmod.reduce(oth+MOD-dp[n][0].a) << '\n';
}

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