QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#434387#8792. Candiesucup-team3564#AC ✓2934ms4336kbC++142.4kb2024-06-08 16:00:492024-06-08 16:00:50

Judging History

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

  • [2024-06-08 16:00:50]
  • 评测
  • 测评结果:AC
  • 用时:2934ms
  • 内存:4336kb
  • [2024-06-08 16:00:49]
  • 提交

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