QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#685933#8792. CandieshhoppitreeAC ✓1957ms4416kbC++171.4kb2024-10-28 22:01:022024-10-28 22:01:02

Judging History

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

  • [2024-10-28 22:01:02]
  • 评测
  • 测评结果:AC
  • 用时:1957ms
  • 内存:4416kb
  • [2024-10-28 22:01:02]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 3e4 + 5, P = 998244353;

int pw[N], fac[N], inv[N], iFac[N];

int C(int x, int y, int z) {
    return 1ll * fac[x + y + z] * iFac[x] % P * iFac[y] % P * iFac[z] % P;
}

int f(int x, int y, int z) {
    if (x < y || x < z || x < 0 || y < 0 || z < 0) return 0;
    if (x == y) {
        return 1ll * fac[x + x + z] * iFac[x] % P * iFac[x + 1] % P * iFac[z] % P * pw[z + z] % P * fac[x] % P * iFac[x - z] % P * fac[x] % P * iFac[x - z] % P * iFac[x + x + 1] % P * fac[x + x + 1 - z - z] % P;
    }
    int res = C(x, y, z);
    for (int i = 0; i < y; ++i) {
        for (int j = 0; j <= z; ++j) {
            res = (res - 1ll * C(x - i, y - (i + 1), z - j) * f(i, i, j) + P) % P;
        }
    }
    for (int i = 0; i < z; ++i) {
        for (int j = 0; j <= y; ++j) {
            res = (res - 1ll * C(x - i, z - (i + 1), y - j) * f(i, i, j) + P) % P;
        }
    }
    return (res % P + P) % P;
}

signed main() {
    for (int i = pw[0] = fac[0] = 1; i < N; ++i) {
        pw[i] = 2ll * pw[i - 1] % P;
        fac[i] = 1ll * fac[i - 1] * i % P;
        inv[i] = (i == 1 ? 1 : 1ll * inv[P % i] * (P - P / i) % P);
    }
    for (int i = iFac[0] = 1; i < N; ++i) {
        iFac[i] = 1ll * iFac[i - 1] * inv[i] % P;
    }
    int p, q, r; scanf("%d%d%d", &p, &q, &r);
    printf("%d\n", f(p, q, r));
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4276kb

input:

4 3 2

output:

368

result:

ok answer is '368'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4336kb

input:

10000 10000 10000

output:

905642282

result:

ok answer is '905642282'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4284kb

input:

99 99 99

output:

604759627

result:

ok answer is '604759627'

Test #4:

score: 0
Accepted
time: 1957ms
memory: 4344kb

input:

10000 9876 6543

output:

172894229

result:

ok answer is '172894229'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4336kb

input:

7 1 6

output:

5577

result:

ok answer is '5577'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4344kb

input:

28 23 17

output:

816429586

result:

ok answer is '816429586'

Test #7:

score: 0
Accepted
time: 1ms
memory: 4228kb

input:

87 54 22

output:

401507657

result:

ok answer is '401507657'

Test #8:

score: 0
Accepted
time: 1ms
memory: 4288kb

input:

50 40 16

output:

770938562

result:

ok answer is '770938562'

Test #9:

score: 0
Accepted
time: 1ms
memory: 4256kb

input:

72 19 53

output:

607733148

result:

ok answer is '607733148'

Test #10:

score: 0
Accepted
time: 1ms
memory: 4280kb

input:

8 4 4

output:

325590

result:

ok answer is '325590'

Test #11:

score: 0
Accepted
time: 1ms
memory: 4220kb

input:

65 45 14

output:

452076388

result:

ok answer is '452076388'

Test #12:

score: 0
Accepted
time: 1ms
memory: 4284kb

input:

82 8 67

output:

708832480

result:

ok answer is '708832480'

Test #13:

score: 0
Accepted
time: 1ms
memory: 4404kb

input:

65 10 35

output:

769016918

result:

ok answer is '769016918'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4312kb

input:

4 3 4

output:

1408

result:

ok answer is '1408'

Test #15:

score: 0
Accepted
time: 54ms
memory: 4404kb

input:

9139 6356 279

output:

833879698

result:

ok answer is '833879698'

Test #16:

score: 0
Accepted
time: 142ms
memory: 4204kb

input:

3888 2407 1937

output:

380556889

result:

ok answer is '380556889'

Test #17:

score: 0
Accepted
time: 755ms
memory: 4332kb

input:

9161 3171 7913

output:

643956900

result:

ok answer is '643956900'

Test #18:

score: 0
Accepted
time: 32ms
memory: 4352kb

input:

1392 1354 938

output:

491399135

result:

ok answer is '491399135'

Test #19:

score: 0
Accepted
time: 15ms
memory: 4272kb

input:

5930 427 1403

output:

786969030

result:

ok answer is '786969030'

Test #20:

score: 0
Accepted
time: 1ms
memory: 4348kb

input:

507 99 150

output:

960656496

result:

ok answer is '960656496'

Test #21:

score: 0
Accepted
time: 193ms
memory: 4328kb

input:

3119 2372 2681

output:

751161512

result:

ok answer is '751161512'

Test #22:

score: 0
Accepted
time: 306ms
memory: 4408kb

input:

6636 3688 2743

output:

839083240

result:

ok answer is '839083240'

Test #23:

score: 0
Accepted
time: 38ms
memory: 4416kb

input:

4890 475 2865

output:

788640273

result:

ok answer is '788640273'

Test #24:

score: 0
Accepted
time: 127ms
memory: 4284kb

input:

6708 663 6384

output:

426276232

result:

ok answer is '426276232'

Test #25:

score: 0
Accepted
time: 1ms
memory: 4284kb

input:

1 1 1

output:

2

result:

ok answer is '2'

Extra Test:

score: 0
Extra Test Passed