QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#714418#9566. Topologyucup-team1196RE 30ms5244kbC++232.0kb2024-11-05 23:09:002024-11-05 23:09:00

Judging History

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

  • [2024-11-05 23:09:00]
  • 评测
  • 测评结果:RE
  • 用时:30ms
  • 内存:5244kb
  • [2024-11-05 23:09:00]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N=2009,mod=998244353;
int fac[N],invfac[N];
int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}

void init(){
    fac[0]=invfac[0]=1;
    for(int i=1;i<=N-8;++i) fac[i]=fac[i-1]*i%mod;
    invfac[N-8]=qpow(fac[N-8],mod-2);
    for(int i=N-8;i;--i) invfac[i-1]=invfac[i]*i%mod;
}

int C(int x,int y){
    if(x<y) return 0;
    return fac[x]*invfac[x-y]%mod*invfac[y]%mod;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    init();
    int n;
    cin>>n;
    vector<vector<int>>e(n+1);
    for(int i=2;i<=n;++i){
        int x;
        cin>>x;
        e[x].push_back(i);
    }
    vector<int>sz(n+1),f(n+1),dep(n+1);
    vector g(n+1,vector(n+1,0ll));
    dep[1]=1;
    auto dfs=[&](auto dfs,int u)->void{
        sz[u]=1;
        f[u]=1;
        for(auto v:e[u]){
            dep[v]=dep[u]+1;
            dfs(dfs,v);
            sz[u]+=sz[v];
            f[u]=f[u]*f[v]%mod*invfac[sz[v]]%mod;
        }
        f[u]=f[u]*fac[sz[u]-1]%mod;
    };
    dfs(dfs,1);
    g[1][1]=1;
    auto dfs2=[&](auto dfs2,int u)->void{
        int sf=1,sfac=1;
        for(auto v:e[u]){
            sf=sf*f[v]%mod;
            sfac=sfac*invfac[sz[v]]%mod;
        }
        for(auto v:e[u]){
            for(int i=dep[u];i<=n-sz[u]+1;++i){
                int ans=g[u][i]*C(n-i-sz[v],sz[u]-sz[v]-1)%mod;
                ans=ans*sf%mod*qpow(f[v],mod-2)%mod;
                ans=ans*sfac%mod*fac[sz[v]]%mod*fac[sz[u]-1-sz[v]]%mod;
                g[v][i+1]+=ans;
                if(g[v][i+1]>=mod) g[v][i+1]-=mod;
            }
            for(int i=dep[v]+1;i<=n-sz[v]+1;++i){
                g[v][i]+=g[v][i-1];
                if(g[v][i]>=mod) g[v][i]-=mod;
            }
            dfs2(dfs2,v);
        }
    };
    dfs2(dfs2,1);
    for(int i=1;i<=n;++i) cout<<f[i]*g[i][i]%mod*C(n-i,sz[i]-1)%mod<<" \n"[i==n];
}

详细

Test #1:

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

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: 0ms
memory: 3608kb

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: 3652kb

input:

2
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #4:

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

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: 17ms
memory: 5176kb

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: 13ms
memory: 5192kb

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: 30ms
memory: 5156kb

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: 2ms
memory: 5144kb

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: 28ms
memory: 5176kb

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: 25ms
memory: 5244kb

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: -100
Runtime Error

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:


result: