QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#434386 | #8792. Candies | ucup-team3564# | RE | 1ms | 3792kb | C++14 | 2.4kb | 2024-06-08 16:00:31 | 2024-06-08 16:00:32 |
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 = 1e4;
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);
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3792kb
input:
4 3 2
output:
368
result:
ok answer is '368'
Test #2:
score: -100
Runtime Error
input:
10000 10000 10000