QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#621580#8635. 圆Kryptonite100 ✓77ms3820kbC++201.6kb2024-10-08 15:29:402024-10-08 15:30:02

Judging History

你现在查看的是最新测评结果

  • [2024-10-08 15:30:02]
  • 评测
  • 测评结果:100
  • 用时:77ms
  • 内存:3820kb
  • [2024-10-08 15:29:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5005;
const int mod = 998244353;

int n;
ll fac[N], inv[N], sum[N];

void add(ll &x, ll y) {
	x = x + y >= mod ? x + y - mod : x + y;
}

ll qpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}

ll C(int x, int y) {
	if (x < y) return 0ll;
	return fac[x] * inv[y] % mod * inv[x - y] % mod;
}

signed main() {
//	freopen("color.in", "r", stdin);
//	freopen("color.out", "w", stdout);
	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n;
	if (n == 3) {
		cout << 1;
		return 0;
	}
	// define the first step is on the first.
	fac[0] = inv[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = qpow(fac[i], mod - 2);
	}
	for (int k = 1; k < n; ++k) {
		// calc the answer less than k yet the first one.
		ll g = 0;
		for (int ed = n - 2; ed <= n; ++ed) {
			int len = ed - 1;
			for (int a = 0; a <= len && a <= k; ++a) {
				int b2c = len - k;
				int bc = k - a;
				int c = b2c - bc;
				int b = k - a - c;
				if (b >= 0 && c >= 0) {
					g = (g + C(k, a) * C(k - a, b) % mod * fac[k] % mod) % mod;
				}
			}
		}
		sum[k + 1] = g * fac[n - k - 1] % mod;
	}
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
//		cout << i << " : " << sum[i] - sum[i - 1] << '\n';
		ll tmp = (sum[i] - sum[i - 1] + mod) * inv[n - 1] % mod;
//		cout << tmp << " ON EARTH.\n";
		ans = (ans + tmp * i % mod) % mod;
	}
	cout << ans;
	
	return 0;
}

详细


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 3512kb

input:

3

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 10
Accepted
time: 0ms
memory: 3588kb

input:

4

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 10
Accepted
time: 0ms
memory: 3588kb

input:

6

output:

299473309

result:

ok 1 number(s): "299473309"

Test #4:

score: 10
Accepted
time: 0ms
memory: 3656kb

input:

10

output:

487238321

result:

ok 1 number(s): "487238321"

Test #5:

score: 10
Accepted
time: 0ms
memory: 3588kb

input:

100

output:

41620761

result:

ok 1 number(s): "41620761"

Test #6:

score: 10
Accepted
time: 0ms
memory: 3604kb

input:

200

output:

208771764

result:

ok 1 number(s): "208771764"

Test #7:

score: 10
Accepted
time: 1ms
memory: 3656kb

input:

500

output:

888621375

result:

ok 1 number(s): "888621375"

Test #8:

score: 10
Accepted
time: 71ms
memory: 3692kb

input:

4798

output:

319137015

result:

ok 1 number(s): "319137015"

Test #9:

score: 10
Accepted
time: 73ms
memory: 3700kb

input:

4999

output:

818467659

result:

ok 1 number(s): "818467659"

Test #10:

score: 10
Accepted
time: 77ms
memory: 3820kb

input:

5000

output:

142907477

result:

ok 1 number(s): "142907477"