QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#621580 | #8635. 圆 | Kryptonite | 100 ✓ | 77ms | 3820kb | C++20 | 1.6kb | 2024-10-08 15:29:40 | 2024-10-08 15:30:02 |
Judging History
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"