QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#753159#9120. Huge Segment TreecpismylifeOwORE 1ms7820kbC++231.5kb2024-11-16 11:35:092024-11-16 11:35:09

Judging History

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

  • [2024-11-16 11:35:09]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7820kb
  • [2024-11-16 11:35:09]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const long long mod = 998244353;
const int MaxN = 1e6 + 5;

int k;

void Inp()
{
    cin >> k;
}

long long Pow2[MaxN];
long long Fact[MaxN];
long long RevFact[MaxN];

long long C(long long k, long long n)
{
    if (k > n)
    {
        return 0;
    }
    return ((Fact[n] * RevFact[n - k]) % mod * RevFact[k]) % mod;
}

void Exc()
{
    Pow2[0] = Fact[0] = 1;
    for (int x = 1; x <= 3 * k; x++)
    {
        Pow2[x] = (Pow2[x - 1] * 2) % mod;
        Fact[x] = (Fact[x - 1] * x) % mod;
    }
    RevFact[1] = 1;
    for (int x = 2; x <= 3 * k; x++)
    {
        RevFact[x] = (mod - (mod / x) * RevFact[mod % x] % mod) % mod;
    }
    RevFact[0] = 1;
    for (int x = 1; x <= 3 * k; x++)
    {
        RevFact[x] = (RevFact[x - 1] * RevFact[x]) % mod;
    }
    cout << Pow2[k + 1] - 1 << " ";
    for (int x = 2; x <= 2 * k - 2; x++)
    {
        long long res = 0;
        for (int y = 0; y < k; y++)
        {
            res = (res + Pow2[k - y - 1] * ((C(x, 2 * y) - 2 * C(x, y) % mod + 2 * C(x - 1, y)) % mod) % mod) % mod;
        }
        cout << (res % mod + mod) % mod << " ";
    }
}

int main()
{
    //freopen("D.INP", "r", stdin);
    //freopen("D.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int w = 1; w <= test; w++)
    {
        Inp();
        Exc();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2

output:

7 3 

result:

ok 2 tokens

Test #2:

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

input:

3

output:

15 14 6 1 

result:

ok 4 tokens

Test #3:

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

input:

4

output:

31 43 36 19 6 1 

result:

ok 6 tokens

Test #4:

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

input:

5

output:

63 110 132 114 70 30 8 1 

result:

ok 8 tokens

Test #5:

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

input:

6

output:

127 255 384 448 400 272 136 47 10 1 

result:

ok 10 tokens

Test #6:

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

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: 1ms
memory: 7724kb

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: 1ms
memory: 7720kb

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: 1ms
memory: 7764kb

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: 1ms
memory: 7688kb

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: