QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#434386#8792. Candiesucup-team3564#RE 1ms3792kbC++142.4kb2024-06-08 16:00:312024-06-08 16:00:32

Judging History

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

  • [2024-06-08 16:00:32]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3792kb
  • [2024-06-08 16:00:31]
  • 提交

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

output:


result: