Submission #796986

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796986	2023-07-29T02:46:58 Z	GusterGoose27	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	100 / 100	4834 ms	1136 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	2 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct

Subtask #5
36.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	2 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	109 ms	396 KB	Output is correct
25	Correct	109 ms	392 KB	Output is correct
26	Correct	108 ms	392 KB	Output is correct
27	Correct	2 ms	212 KB	Output is correct
28	Correct	19 ms	340 KB	Output is correct
29	Correct	15 ms	340 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	2 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	109 ms	396 KB	Output is correct
25	Correct	109 ms	392 KB	Output is correct
26	Correct	108 ms	392 KB	Output is correct
27	Correct	2 ms	212 KB	Output is correct
28	Correct	19 ms	340 KB	Output is correct
29	Correct	15 ms	340 KB	Output is correct
30	Correct	4834 ms	1100 KB	Output is correct
31	Correct	4811 ms	1016 KB	Output is correct
32	Correct	4818 ms	1136 KB	Output is correct
33	Correct	2476 ms	836 KB	Output is correct
34	Correct	453 ms	488 KB	Output is correct
35	Correct	377 ms	472 KB	Output is correct

Submission #796986

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 27.0 / 27.0

Subtask #4 14.0 / 14.0

Subtask #5 36.0 / 36.0

Subtask #6 13.0 / 13.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
27.0 / 27.0

Subtask #4
14.0 / 14.0

Subtask #5
36.0 / 36.0

Subtask #6
13.0 / 13.0