oj.uz

Submission #796983

# Submission time Handle Problem Language Result Execution time Memory
796983 2023-07-29T02:44:32 Z GusterGoose27 Festivals in JOI Kingdom 2 (JOI23_festival2) C++17
0 / 100
 1 ms 212 KB 
#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;
struct FastMod {
	ull b, m;
	FastMod() {}
	FastMod(ull b) : b(b), m(-1ULL / b) {}
	ull reduce(ull a) { // a % b + (0 or b)
		return 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];

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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -