QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#549897#9120. Huge Segment Treeucup-team1766RE 6ms11636kbC++172.2kb2024-09-06 23:13:142024-09-06 23:13:15

Judging History

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

  • [2024-09-06 23:13:15]
  • 评测
  • 测评结果:RE
  • 用时:6ms
  • 内存:11636kb
  • [2024-09-06 23:13:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;
const int MAXN = 500005;

long long fact[MAXN];
long long inv_fact[MAXN];

long long binpow(long long a, long long b) {
    if (b == 0) {
        return 1;
    }
    long long c = binpow(a, b / 2);
    if (b % 2 == 0) {
        return c * c % MOD;
    } else {
        return c * c % MOD * a % MOD;
    }
}

long long modinv(long long a) {
    return binpow(a, MOD - 2);
}

long long nck(int n, int k) {
    if (k > n) {
        return 0;
    }
    return fact[n] * inv_fact[n - k] % MOD * inv_fact[k] % MOD;
}

vector<long long> divide(vector<long long> &p, vector<long long> &q) {
    vector<long long> res(p.size());
    for (int i = p.size() - 1; i >= q.size() - 1; i--) {
        int pow_diff = i - q.size() + 1;
        long long mult_diff = p[i] * modinv(q[q.size() - 1]) % MOD;
        res[pow_diff] = mult_diff;
        for (int j = 0; j < q.size(); j++) {
            p[j + pow_diff] -= q[j] * mult_diff % MOD;
            p[j + pow_diff] = (p[j + pow_diff] + MOD) % MOD;
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    inv_fact[MAXN - 1] = modinv(fact[MAXN - 1]);
    for (int i = MAXN - 2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }

    int K;
    cin >> K;

    vector<long long> p1(K + 2);
    for (int i = 0; i <= K; i++) {
        p1[i] = 2 * nck(K, i) % MOD;
    }
    p1[0] = (p1[0] - binpow(2, K + 1) + MOD) % MOD;

    vector<long long> p2(2 * K + 1);
    for (int i = 0; i <= 2 * K; i++) {
        p2[i] = MOD - nck(2 * K, i);
    }
    p2[0] = (p2[0] + binpow(2, K)) % MOD;
    
    vector<long long> den {1, MOD - 2, MOD - 1};
    vector<long long> quo = divide(p2, den);

    vector<long long> res(2 * K - 1);
    res[0] = binpow(2, K) - 1;
    res[1] = 1;
    for (int i = 1; i <= 2 * K - 2; i++) {
        res[i] += quo[i];
        if (i <= K + 1) {
            res[i] += p1[i];
        }
        res[i] %= MOD;
        cout << res[i] << " ";
    }
    cout << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2

output:

7 3 

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 6ms
memory: 11328kb

input:

3

output:

15 14 6 1 

result:

ok 4 tokens

Test #3:

score: 0
Accepted
time: 6ms
memory: 11592kb

input:

4

output:

31 43 36 19 6 1 

result:

ok 6 tokens

Test #4:

score: 0
Accepted
time: 6ms
memory: 11340kb

input:

5

output:

63 110 132 114 70 30 8 1 

result:

ok 8 tokens

Test #5:

score: 0
Accepted
time: 6ms
memory: 11348kb

input:

6

output:

127 255 384 448 400 272 136 47 10 1 

result:

ok 10 tokens

Test #6:

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

input:

7

output:

255 558 978 1401 1610 1478 1066 589 240 68 12 1 

result:

ok 12 tokens

Test #7:

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

input:

8

output:

511 1179 2292 3803 5250 5987 5576 4183 2482 1137 388 93 14 1 

result:

ok 14 tokens

Test #8:

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

input:

9

output:

1023 2438 5088 9398 14896 20038 22632 21250 16406 10282 5144 2006 588 122 16 1 

result:

ok 16 tokens

Test #9:

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

input:

10

output:

2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1 

result:

ok 18 tokens

Test #10:

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

input:

11

output:

4095 10070 22782 48209 92140 156292 232068 298744 330926 313422 252186 171122 97008 45368 17200 5155 1176 192 20 1 

result:

ok 20 tokens

Test #11:

score: -100
Runtime Error

input:

500000

output:


result: