QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735712#9566. Topologyucup-team4479AC ✓129ms101608kbC++232.2kb2024-11-11 21:22:222024-11-11 21:22:22

Judging History

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

  • [2024-11-11 21:22:22]
  • 评测
  • 测评结果:AC
  • 用时:129ms
  • 内存:101608kb
  • [2024-11-11 21:22:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 5005, mod = 998244353;
int fa[N], siz[N], prod[N], invp[N], fac[N], inv[N];
int g[N][N], dep[N], n, pre[N];
vector <int> E[N];
int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}
int C(int n, int m) {
    return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void dfs(int u) {
    siz[u] = prod[u] = 1;
    dep[u] = dep[fa[u]] + 1;
    for (int v : E[u]) {
        dfs(v);
        siz[u] += siz[v];
        prod[u] = 1ll * prod[u] * prod[v] % mod;
    }
    prod[u] = 1ll * prod[u] * siz[u] % mod;
    invp[u] = power(prod[u], mod - 2);
}
void dp(int u) {
    pre[dep[u] - 1] = 0;
    for (int v : E[u]) {
        int tmp = 1ll * fac[siz[u] - siz[v]] % mod * invp[u] % mod * prod[v] % mod * siz[u] % mod * power(siz[u] - siz[v], mod - 2) % mod;
        for (int x = dep[u]; x <= n - siz[u] + 1; ++x) {
            // if (!g[u][x]) continue;
            pre[x] = (pre[x - 1] + 1ll * C(n - siz[v] - x, siz[u] - siz[v] - 1) * tmp % mod * g[u][x]) % mod;
        }
        for (int x = n - siz[u] + 2; x <= n - siz[v] + 1; ++x) pre[x] = pre[x - 1];
        for (int y = dep[v]; y <= n - siz[v] + 1; ++y) {
            g[v][y] = pre[y - 1];
        }
        dp(v);
    }
}
int main() {
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    cout.tie(0);
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        cin >> fa[i];
        E[fa[i]].push_back(i);
    }
    fac[0] = 1;
    for (int i = 1; i <= n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[n] = power(fac[n], mod - 2);
    for (int i = n; i >= 1; --i)
        inv[i - 1] = 1ll * inv[i] * i % mod;
    dfs(1);
    g[1][1] = 1;
    dp(1);
    // for (int i = 1; i <= n; ++i)
    //     for (int j = dep[i]; j <= n - siz[i] + 1; ++j)
    //         printf("g[%d][%d] = %d\n", i, j, g[i][j]);
    for (int i = 1; i <= n; ++i) {
        int res = 1ll * g[i][i] * C(n - i, siz[i] - 1) % mod * fac[siz[i]] % mod * invp[i] % mod;
        cout << res << endl;
    }
    return 0;
}
/*
4
1 1 2
9
1 1 2 2 3 3 4 5
*/

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

詳細信息

Test #1:

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

input:

4
1 1 2

output:

3
2
1
2

result:

ok 4 number(s): "3 2 1 2"

Test #2:

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

input:

9
1 1 2 2 3 3 4 5

output:

672
420
180
160
152
108
120
170
210

result:

ok 9 numbers

Test #3:

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

input:

2
1

output:

1
1

result:

ok 2 number(s): "1 1"

Test #4:

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

input:

500
1 2 3 4 5 6 7 7 8 10 8 10 11 4 11 12 12 17 15 13 21 21 22 5 16 9 24 28 28 19 29 27 17 33 23 3 33 27 30 9 25 34 16 26 30 34 46 45 41 14 43 49 43 35 39 37 26 48 52 58 51 56 51 55 19 48 63 36 67 69 54 60 71 61 29 40 32 77 73 55 66 42 77 72 71 69 62 83 46 64 88 39 83 36 89 94 47 98 57 61 38 80 78 88...

output:

331058271
331058271
107893248
201481008
579367731
934007150
548415590
60830816
948776140
565765713
126668425
603509050
491206892
433369091
271511598
706737964
70425819
69672788
713120782
734952162
267434947
720007515
670449595
828144080
372921049
434477621
877300187
307269573
636190001
793011806
327...

result:

ok 500 numbers

Test #5:

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

input:

500
1 2 3 4 5 2 6 8 9 10 11 12 13 14 15 16 7 18 19 17 21 20 22 24 25 26 23 27 29 30 2 28 31 34 35 36 37 38 39 33 40 42 41 43 45 46 17 47 49 35 50 52 44 53 9 55 54 57 58 59 61 60 62 64 65 66 67 68 69 70 63 71 27 73 25 70 75 78 79 80 75 80 81 84 72 86 87 85 89 90 91 88 92 16 71 93 53 94 99 10 100 12 9...

output:

199957339
199957339
748333395
805642956
810719215
216632308
964282353
833358220
623717061
424992417
41206958
5217119
281930684
668877517
802111716
240451113
155227928
771617392
672767638
673855602
761694864
890967936
403166179
449035439
448814216
496258330
91156115
884637248
925796040
876356346
3811...

result:

ok 500 numbers

Test #6:

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

input:

500
1 2 1 4 3 6 5 8 7 9 11 10 12 13 15 14 17 16 18 20 21 19 22 24 23 25 26 28 27 30 29 32 33 31 34 36 37 35 38 40 41 42 43 39 44 46 47 45 48 50 49 51 53 54 52 56 55 58 59 60 61 57 63 62 65 66 64 67 69 70 71 72 73 74 75 76 68 77 78 79 81 80 83 84 85 82 87 88 89 86 90 91 93 94 95 96 97 92 99 98 100 10...

output:

187816035
355846039
636462310
682484799
14615667
17420694
667957129
920773234
729673969
411376216
888381123
826027316
567944447
754373007
910160630
717957076
351581515
786718944
83290109
442478607
895300579
856543135
635821052
404405371
646574856
177948738
754298629
824600386
979643534
991141839
946...

result:

ok 500 numbers

Test #7:

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

input:

500
1 2 3 4 5 6 7 6 9 9 11 10 13 14 11 14 17 18 19 5 10 17 20 15 12 22 25 19 18 28 28 32 30 23 15 23 22 30 12 38 35 41 2 38 21 42 40 25 7 27 37 49 41 16 39 50 45 36 59 33 59 16 34 51 35 43 54 4 45 64 20 32 37 74 50 27 24 54 73 26 61 63 68 46 56 60 52 83 66 60 21 51 65 8 92 77 48 88 93 67 53 42 74 10...

output:

427192209
427192209
23428540
404862570
37642846
503529666
371081925
254270895
921949697
428219013
402374560
324846667
395339852
778833345
147767470
733058880
358816361
71418780
554069977
130001346
128392987
484159059
134194129
243653359
516885764
231025182
612595461
494287189
387500567
550886195
417...

result:

ok 500 numbers

Test #8:

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

input:

500
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

329123348
329123348
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
618048964
...

result:

ok 500 numbers

Test #9:

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

input:

500
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 19 19 19 23 19 19 19 27 28 19 19 19 24 32 19 19 35 21 36 40 41 42 39 19 34 29 19 19 19 37 33 26 52 48 44 30 57 46 25 56 22 58 43 54 38 45 61 65 59 62 20 50 60 47 72 75 73 51 66 31 53 49 71 83 63 68 70 55 76 1 64 78 86 74 87 81 94 82 99 89 97 92 ...

output:

853424916
94140539
412971244
235944608
263389091
489983454
601309014
819943428
486761409
617130546
686025380
122859767
819931429
563270436
884428627
886775343
47583182
426881586
177783742
240713239
583332417
714069050
77150690
574574846
465537641
189786313
312927405
763991274
371298436
953710348
715...

result:

ok 500 numbers

Test #10:

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

input:

500
1 2 2 4 2 5 7 8 2 9 11 12 13 14 15 16 17 18 10 19 21 22 2 18 25 2 26 27 23 30 2 31 33 3 34 36 37 38 28 39 2 20 41 44 45 2 40 46 49 48 51 52 25 43 53 29 55 56 46 59 50 62 57 61 54 63 45 45 2 65 71 67 73 59 46 74 77 49 78 77 78 43 81 72 80 84 64 87 77 78 2 2 76 86 62 68 71 95 96 2 82 2 89 60 94 69...

output:

471850367
471850367
182262350
404570423
107733458
816781731
922698877
850608239
433937054
883062365
287376567
851878007
830978534
761469013
140873496
758088636
641403760
236550255
968037976
36602630
940485631
261386090
728452257
816781731
556050534
883310107
938450533
689162937
196110016
463212341
8...

result:

ok 500 numbers

Test #11:

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

input:

5000
1 2 3 4 5 6 7 4 8 7 10 12 10 14 2 15 17 17 18 15 6 21 19 12 14 11 20 20 27 29 28 32 24 34 21 11 33 9 25 13 34 39 42 35 36 44 3 47 9 44 5 38 53 37 41 13 39 38 22 28 57 59 54 59 61 66 54 64 58 26 49 23 62 25 69 73 48 45 67 77 68 23 24 81 71 47 87 62 73 65 55 88 74 36 95 29 26 75 80 32 66 87 75 98...

output:

213868945
268027508
172098586
429180541
421578947
50365364
164645256
375568069
380340202
794392454
631058887
732429296
764758041
679179700
323937623
630630580
728260271
644709492
780995578
920119920
385808637
743058413
845082711
505702526
771349695
612467484
721600573
582663824
373483262
215394153
4...

result:

ok 5000 numbers

Test #12:

score: 0
Accepted
time: 82ms
memory: 101564kb

input:

5000
1 2 1 3 4 5 6 7 8 10 9 11 13 12 14 15 17 18 19 20 16 21 23 24 25 26 27 22 29 28 31 32 33 34 30 36 37 35 38 39 40 42 43 41 45 44 46 47 48 49 51 50 53 54 52 56 55 57 59 58 61 60 62 64 65 63 67 66 68 69 70 72 73 71 75 76 77 78 79 80 81 82 83 84 74 85 86 87 88 88 90 89 92 94 54 95 93 98 99 100 97 1...

output:

34320817
849212971
727124959
103502088
722548602
437600262
727984738
403178199
175442071
47161554
155808815
844742230
392754083
112293444
611825478
800939828
515364345
521125243
346555616
971721903
513651560
282097354
912292406
397744600
218091070
728191250
854235177
778102777
540096076
768522784
40...

result:

ok 5000 numbers

Test #13:

score: 0
Accepted
time: 39ms
memory: 101472kb

input:

5000
1 1 2 4 5 6 7 8 9 10 11 12 13 3 14 16 17 18 19 15 20 22 21 23 25 26 27 28 29 30 31 32 33 34 35 36 24 37 39 38 41 42 40 44 45 46 47 48 49 50 51 43 52 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 53 84 86 87 85 88 89 91 92 90 94 95 96 97 98 99 100 101 ...

output:

135540780
120808213
297369580
981542355
598035888
571082645
993830824
16223792
897295303
894126562
181120714
574618105
327832029
633825222
693625787
981484899
383128792
445971843
428737681
890587552
637760855
929571700
498202822
463712869
220090138
58569622
25359841
555969251
458869880
441439833
491...

result:

ok 5000 numbers

Test #14:

score: 0
Accepted
time: 123ms
memory: 101556kb

input:

5000
1 2 3 4 2 5 5 8 5 9 5 9 11 13 8 16 13 16 11 13 19 15 18 9 16 4 17 12 12 21 16 18 17 4 28 11 13 7 25 38 25 34 19 7 12 9 26 47 10 50 4 19 45 37 7 35 10 28 24 58 32 62 35 28 29 44 12 7 22 31 66 32 47 30 39 23 23 18 19 18 25 39 47 32 74 79 47 74 21 53 75 48 82 73 38 44 3 29 52 40 29 17 26 20 21 96 ...

output:

510653214
689165782
371773375
981160094
888202589
808944221
521342567
421321748
656514338
712869283
51659539
470618625
116807666
435525700
885128226
117287052
568157666
481074203
850765463
472698368
63610114
466384863
106895675
311520030
86048918
486016964
464169978
238357962
56730023
199676513
3659...

result:

ok 5000 numbers

Test #15:

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

input:

5000
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

759746016
759746016
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
420780783
...

result:

ok 5000 numbers

Test #16:

score: 0
Accepted
time: 129ms
memory: 101260kb

input:

5000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 74 74 74 74 74 75 74 74 82 74 74 74 74 74 74 85 90 88 93 76 80 74 74 74 74 100 74 ...

output:

195719530
862840687
531717491
200594295
867715452
536592256
205469060
872590217
541467021
210343825
877464982
546341786
215218590
882339747
551216551
220093355
887214512
556091316
224968120
892089277
560966081
229842885
896964042
565840846
234717650
901838807
570715611
239592415
906713572
575590376
...

result:

ok 5000 numbers

Test #17:

score: 0
Accepted
time: 95ms
memory: 100964kb

input:

5000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 27 30 32 1 33 35 36 37 27 38 40 41 42 31 43 45 46 47 48 49 50 51 52 53 54 27 27 55 56 58 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 27 82 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

output:

991852391
349488018
982737491
375923871
420447688
369611759
356619577
345494408
79666905
647061157
602149888
751358978
14418819
314194382
971982920
681362711
287707304
885936382
165011934
952932924
125116857
505772130
20550804
746107002
212042197
335897693
915079069
113298941
157136915
21971818
5470...

result:

ok 5000 numbers

Extra Test:

score: 0
Extra Test Passed