QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#434387 | #8792. Candies | ucup-team3564# | AC ✓ | 2934ms | 4336kb | C++14 | 2.4kb | 2024-06-08 16:00:49 | 2024-06-08 16:00:50 |
Judging History
answer
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int mod = 998244353;
int norm(int x) { return x >= mod ? x - mod : x; }
int reduce(int x) { return x < 0 ? x + mod : x; }
int neg(int x) { return x ? mod - x : 0; }
int quo2(int x) { return (x + (x & 1 ? mod : 0)) >> 1; }
void add(int &x, int y) { x += y, x = x >= mod ? x - mod : x; }
void sub(int &x, int y) { x -= y, x = x < 0 ? x + mod : x; }
void fam(int &x, int y, int z) { x = (x + (ll)y * z) % mod; }
int mpow(int a, int b) {
int ret = 1;
for (; b; b >>= 1) {
if (b & 1) ret = (ll)ret * a % mod;
a = (ll)a * a % mod;
}
return ret;
}
const int N = 3e4;
int n, a, b, c;
int fac[N + 5], ifac[N + 5], inv[N + 5];
int pw4[N + 5];
int ans;
int Q(int i, int n) {
if (i < 0 || n < i * 2 || (n - i * 2) % 3) return 0;
int m = (n - i * 2) / 3;
return (ll)pw4[m] * (i * 2 + 1) % mod * inv[m + i + 1] % mod * inv[m * 2 + i * 2 + 1] % mod * fac[i * 2] % mod * ifac[i] % mod * ifac[i] % mod * fac[n] % mod * ifac[m] % mod * ifac[n - m] % mod;
}
int main() {
scanf("%d%d%d", &c, &a, &b), n = a + b + c, a = c - a, b = c - b;
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % mod;
ifac[n] = mpow(fac[n], mod - 2);
for (int i = n; i; --i) ifac[i - 1] = (ll)ifac[i] * i % mod;
for (int i = 1; i <= n; ++i) inv[i] = (ll)ifac[i] * fac[i - 1] % mod;
pw4[0] = 1;
for (int i = 1; i <= n; ++i) pw4[i] = 4ll * pw4[i - 1] % mod;
for (int i = 0; i * 3 <= n * 2 - a - b; ++i) {
int j = (n * 2 - a - b) / 3 - i;
int k = n - i - j;
int binom = (ll)fac[n] * ifac[i] % mod * ifac[j] % mod * ifac[k] % mod;
if (k - i == a && k - j == b)
add(ans, binom);
}
for (int i = 0; i * 3 <= n * 2 - a - b - 3; ++i) {
int j = (n * 2 - a - b - 3) / 3 - i;
int k = n - i - j;
int binom = (ll)fac[n] * ifac[i] % mod * ifac[j] % mod * ifac[k] % mod;
if (k - i - 2 == a && k - j - 1 == b)
sub(ans, binom);
if (k - i - 1 == a && k - j - 2 == b)
add(ans, binom);
}
for (int i = 0; i <= n; ++i)
for (int j = 0; i + j <= n; ++j) {
int k = j + b + 1;
if (i + j + k > n) continue;
int binom = (ll)fac[i + j + k] * ifac[i] % mod * ifac[j] % mod * ifac[k] % mod;
ans = (ans + (ll)(mod - 2) * binom % mod * Q(a - k + i, n - 1 - i - j - k)) % mod;
}
printf("%d\n", ans);
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3904kb
input:
4 3 2
output:
368
result:
ok answer is '368'
Test #2:
score: 0
Accepted
time: 2934ms
memory: 4336kb
input:
10000 10000 10000
output:
905642282
result:
ok answer is '905642282'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
99 99 99
output:
604759627
result:
ok answer is '604759627'
Test #4:
score: 0
Accepted
time: 1606ms
memory: 4300kb
input:
10000 9876 6543
output:
172894229
result:
ok answer is '172894229'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
7 1 6
output:
5577
result:
ok answer is '5577'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
28 23 17
output:
816429586
result:
ok answer is '816429586'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
87 54 22
output:
401507657
result:
ok answer is '401507657'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
50 40 16
output:
770938562
result:
ok answer is '770938562'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
72 19 53
output:
607733148
result:
ok answer is '607733148'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
8 4 4
output:
325590
result:
ok answer is '325590'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
65 45 14
output:
452076388
result:
ok answer is '452076388'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
82 8 67
output:
708832480
result:
ok answer is '708832480'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
65 10 35
output:
769016918
result:
ok answer is '769016918'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
4 3 4
output:
1408
result:
ok answer is '1408'
Test #15:
score: 0
Accepted
time: 162ms
memory: 4088kb
input:
9139 6356 279
output:
833879698
result:
ok answer is '833879698'
Test #16:
score: 0
Accepted
time: 125ms
memory: 3996kb
input:
3888 2407 1937
output:
380556889
result:
ok answer is '380556889'
Test #17:
score: 0
Accepted
time: 1180ms
memory: 4212kb
input:
9161 3171 7913
output:
643956900
result:
ok answer is '643956900'
Test #18:
score: 0
Accepted
time: 29ms
memory: 3900kb
input:
1392 1354 938
output:
491399135
result:
ok answer is '491399135'
Test #19:
score: 0
Accepted
time: 49ms
memory: 4016kb
input:
5930 427 1403
output:
786969030
result:
ok answer is '786969030'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
507 99 150
output:
960656496
result:
ok answer is '960656496'
Test #21:
score: 0
Accepted
time: 200ms
memory: 3932kb
input:
3119 2372 2681
output:
751161512
result:
ok answer is '751161512'
Test #22:
score: 0
Accepted
time: 293ms
memory: 4156kb
input:
6636 3688 2743
output:
839083240
result:
ok answer is '839083240'
Test #23:
score: 0
Accepted
time: 116ms
memory: 4020kb
input:
4890 475 2865
output:
788640273
result:
ok answer is '788640273'
Test #24:
score: 0
Accepted
time: 467ms
memory: 4084kb
input:
6708 663 6384
output:
426276232
result:
ok answer is '426276232'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
1 1 1
output:
2
result:
ok answer is '2'
Extra Test:
score: 0
Extra Test Passed