QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178414 | #6678. Gem Island 2 | ucup-team004# | AC ✓ | 1012ms | 298016kb | C++20 | 2.0kb | 2023-09-13 23:20:07 | 2024-10-14 17:59:12 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int P = 998244353;
int power(int a, int b) {
int res = 1;
for (; b; b /= 2, a = 1LL * a * a % P) {
if (b % 2) {
res = 1LL * res * a % P;
}
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, d, r;
std::cin >> n >> d >> r;
const int N = n + d;
std::vector<int> fac(N + 1), invfac(N + 1);
fac[0] = 1;
for (int i = 1; i <= N; i++) {
fac[i] = 1LL * fac[i - 1] * i % P;
}
invfac[N] = power(fac[N], P - 2);
for (int i = N; i; i--) {
invfac[i - 1] = 1LL * invfac[i] * i % P;
}
auto binom = [&](int n, int m) -> int {
if (n < m || m < 0) {
return 0;
}
return 1LL * fac[n] * invfac[m] % P * invfac[n - m] % P;
};
int ans = 0;
std::vector<int> f(std::max(n, d) + 1);
for (int i = 1; i <= d; i++) {
f[i] = binom(n - 1 + d - i, n - 1);
}
std::vector<bool> isprime(d + 1, true);
for (int p = 2; p <= d; p++) {
if (isprime[p]) {
for (int i = 2 * p; i <= d; i += p) {
isprime[i] = false;
}
for (int i = d / p; i >= 1; i--) {
f[i] = (f[i] + f[i * p]) % P;
}
}
}
for (int i = 1; i <= n; i++) {
f[i] = 1LL * (f[i] + binom(n - 1 + d, n - 1)) * binom(n, i) % P;
}
for (int i = 1; i <= n; i++) {
int res = f[i];
if (i == 1) {
ans = (ans + res) % P;
}
if (i >= r + 1) {
ans = (ans + 1LL * res * (r - i + P) % P * binom(i - 1, i - r - 1) % P * ((i - r - 1) % 2 ? P - 1 : 1)) % P;
ans = (ans + 1LL * res * i % P * binom(i - 2, i - r - 2) % P * ((i - r - 1) % 2 ? P - 1 : 1)) % P;
}
}
ans = 1LL * ans * power(binom(n - 1 + d, n - 1), P - 2) % P;
std::cout << ans << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3480kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 4ms
memory: 4372kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 49ms
memory: 25728kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 49ms
memory: 25728kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 35ms
memory: 19908kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 863ms
memory: 297912kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 5ms
memory: 5152kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 0ms
memory: 5136kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 3ms
memory: 4412kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 47ms
memory: 22948kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 49ms
memory: 22928kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 29ms
memory: 15460kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 1012ms
memory: 298016kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 1011ms
memory: 297992kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 1003ms
memory: 296564kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 835ms
memory: 297972kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"
Extra Test:
score: 0
Extra Test Passed