QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178414#6678. Gem Island 2ucup-team004#AC ✓1012ms298016kbC++202.0kb2023-09-13 23:20:072024-10-14 17:59:12

Judging History

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

  • [2024-10-14 17:59:12]
  • 管理员手动重测该提交记录
  • 测评结果:AC
  • 用时:1012ms
  • 内存:298016kb
  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2023-09-13 23:20:09]
  • 评测
  • 测评结果:100
  • 用时:1002ms
  • 内存:298100kb
  • [2023-09-13 23:20:07]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 998244353;

int power(int a, int b) {
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % P) {
        if (b % 2) {
            res = 1LL * res * a % P;
        }
    }
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, d, r;
    std::cin >> n >> d >> r;
    
    const int N = n + d;
    
    std::vector<int> fac(N + 1), invfac(N + 1);
    fac[0] = 1;
    for (int i = 1; i <= N; i++) {
        fac[i] = 1LL * fac[i - 1] * i % P;
    }
    invfac[N] = power(fac[N], P - 2);
    for (int i = N; i; i--) {
        invfac[i - 1] = 1LL * invfac[i] * i % P;
    }
    
    auto binom = [&](int n, int m) -> int {
        if (n < m || m < 0) {
            return 0;
        }
        return 1LL * fac[n] * invfac[m] % P * invfac[n - m] % P;
    };
    
    int ans = 0;
    std::vector<int> f(std::max(n, d) + 1);
    for (int i = 1; i <= d; i++) {
        f[i] = binom(n - 1 + d - i, n - 1);
    }
    std::vector<bool> isprime(d + 1, true);
    for (int p = 2; p <= d; p++) {
        if (isprime[p]) {
            for (int i = 2 * p; i <= d; i += p) {
                isprime[i] = false;
            }
            for (int i = d / p; i >= 1; i--) {
                f[i] = (f[i] + f[i * p]) % P;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        f[i] = 1LL * (f[i] + binom(n - 1 + d, n - 1)) * binom(n, i) % P;
    }
    for (int i = 1; i <= n; i++) {
        int res = f[i];
        if (i == 1) {
            ans = (ans + res) % P;
        }
        if (i >= r + 1) {
            ans = (ans + 1LL * res * (r - i + P) % P * binom(i - 1, i - r - 1) % P * ((i - r - 1) % 2 ? P - 1 : 1)) % P;
            ans = (ans + 1LL * res * i % P * binom(i - 2, i - r - 2) % P * ((i - r - 1) % 2 ? P - 1 : 1)) % P;
        }
    }
    ans = 1LL * ans * power(binom(n - 1 + d, n - 1), P - 2) % P;
    std::cout << ans << "\n";
    
    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3480kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

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

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

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

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

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

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

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

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

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

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

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

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

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

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 4ms
memory: 4372kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 49ms
memory: 25728kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 49ms
memory: 25728kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 35ms
memory: 19908kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 863ms
memory: 297912kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

score: 0
Accepted
time: 5ms
memory: 5152kb

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

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

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

score: 0
Accepted
time: 3ms
memory: 4412kb

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 47ms
memory: 22948kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 49ms
memory: 22928kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

score: 0
Accepted
time: 29ms
memory: 15460kb

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: 0
Accepted
time: 1012ms
memory: 298016kb

input:

15000000 14999999 514

output:

143843956

result:

ok 1 number(s): "143843956"

Test #21:

score: 0
Accepted
time: 1011ms
memory: 297992kb

input:

14985345 14999998 145124

output:

785676527

result:

ok 1 number(s): "785676527"

Test #22:

score: 0
Accepted
time: 1003ms
memory: 296564kb

input:

14855345 14993298 1451424

output:

779861797

result:

ok 1 number(s): "779861797"

Test #23:

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

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #24:

score: 0
Accepted
time: 835ms
memory: 297972kb

input:

15000000 15000000 15000000

output:

30000000

result:

ok 1 number(s): "30000000"

Extra Test:

score: 0
Extra Test Passed