QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#883874#7772. 意念力huaxiamengjin40 33ms20088kbC++142.1kb2025-02-05 19:34:282025-02-05 19:34:29

Judging History

This is the latest submission verdict.

  • [2025-02-05 19:34:29]
  • Judged
  • Verdict: 40
  • Time: 33ms
  • Memory: 20088kb
  • [2025-02-05 19:34:28]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int NN=998244353;
int dfn[100100],st[20][100100];
int dep[100100],dis[100100];
vector<pair<int,int> >g[100100];
int id[100100],f[100100],ct[100100],tot;

int p[100100],ni[100100];
int mi(int x,int y){
    int sum=1;
    for (;y;y>>=1,x=x*x%NN)
    if(y&1)sum=sum*x%NN;
    return sum;
}
int n,k;
void dfs(int x,int pa){
    dfn[x]=++tot;st[0][tot]=pa;
    for(auto i:g[x]){
        int y=i.first,z=i.second;
        if(y!=pa){
            dis[y]=dis[x]+z;
            dep[y]=dep[x]+1;
            dfs(y,x);
        }
    }
}
int demin(int x,int y){
    return (dep[x]<dep[y])?x:y;
}
int glca(int x,int y){
    if(x==y)return x;
    x=dfn[x],y=dfn[y];
    if(x>y)swap(x,y);
    int tmp=__lg(y-x);
    return demin(st[tmp][x+1],st[tmp][y-(1<<tmp)+1]);
}
int ds(int x,int y){
    return dis[x]+dis[y]-2*dis[glca(x,y)];
}
void init(){
    for (int i=1;i<=__lg(n);i++)
    for (int j=1;j+(1<<i)-1<=n;j++)
    st[i][j]=demin(st[i-1][j],st[i-1][j+(1<<i-1)]);
}
bool cmp(int x,int y){
    return dis[x]<dis[y];
}
int c(int x,int y){
    if(x<0||y<0||x<y)return 0;
    return p[x]*ni[y]%NN*ni[x-y]%NN;
}
signed main(){
    cin>>n>>k;
    for (int i=1,x,y,z;i<n;i++)
    cin>>x>>y>>z,
    g[x].push_back({y,z}),
    g[y].push_back({x,z});
    dfs(1,1);
    init();
    p[0]=1;
    for (int i=1;i<=n;i++)
    p[i]=p[i-1]*i%NN;
    ni[n]=mi(p[n],NN-2);
    for (int i=n;i;i--)
    ni[i-1]=ni[i]*i%NN;
    for (int i=1;i<=n;i++)
    id[i]=i;
    sort(id+1,id+n+1,cmp);
    for (int i=1;i<=n;i++){
        for(int j=1;j<i;j++)
        if(ds(id[i],id[j])<k)ct[i]++;
        // cout<<i<<"@@@"<<ct[i]<<"\n";
    }
    for (int i=0;i<=n;i++){
        f[i]=1;
        for (int j=1;j<=n;j++)
        f[i]=f[i]*(i-ct[j])%NN;
    // cout<<i<<"!!!"<<f[i]<<"\n";
    }
    for (int i=1;i<=n;i++){
        for (int j=0;j<i;j++){
            f[i]=(f[i]-c(i,j)*f[j])%NN;
        }
        f[i]=(f[i]+NN)%NN;
        // cout<<sum<<"~~~~\n";
        cout<<f[i]*ni[i]%NN<<" ";
    }
    cout<<"\n";
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 13904kb

input:

10 586964961
10 4 500997470
4 5 361413298
5 3 239036149
5 6 187680375
3 1 199761661
1 2 459686305
6 7 8390746
7 8 59889425
7 9 419949781

output:

0 0 0 0 192 708 636 203 25 1 

result:

ok 10 numbers

Test #2:

score: 10
Accepted
time: 1ms
memory: 11860kb

input:

10 496325758
3 10 66740689
10 7 456797411
7 9 33319567
9 8 23850338
7 4 698698151
9 6 85638167
4 1 239701723
6 5 11453081
1 2 27039301

output:

0 0 0 0 720 1680 1110 282 29 1 

result:

ok 10 numbers

Test #3:

score: 10
Accepted
time: 1ms
memory: 13904kb

input:

10 206036637
1 4 60775873
1 9 331998567
1 3 106469067
4 10 157533279
3 6 296084755
3 8 488192398
6 7 215556090
6 5 209447883
5 2 1467187

output:

0 0 972 8244 16270 11846 3815 579 40 1 

result:

ok 10 numbers

Subtask #2:

score: 15
Accepted

Test #4:

score: 15
Accepted
time: 33ms
memory: 18116kb

input:

2000 4
325 968 1
968 1118 1
325 430 1
325 1693 1
430 676 1
430 199 1
1693 631 1
631 362 1
325 385 1
676 1441 1
199 1087 1
430 1583 1
1118 674 1
968 1690 1
325 1340 1
199 1718 1
1340 987 1
1690 34 1
362 607 1
607 277 1
34 718 1
1583 1804 1
987 498 1
607 1567 1
362 1332 1
1583 1443 1
607 1920 1
430 76...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 34396558 560597970 342257989 111016545 648115845 896789689 629359408 787287175 225051136 369808516 679693851 350349341 87270678 655949285 424883363 48112584 924467409 910138594 952274861 286758842 346948302 140881427 121554860 465126000 481298451 326871880 970926640...

result:

ok 2000 numbers

Test #5:

score: 15
Accepted
time: 31ms
memory: 17984kb

input:

2000 72
1430 1960 1
1960 1174 1
1174 1305 1
1430 696 1
696 58 1
696 1185 1
1430 610 1
1185 1512 1
1430 1358 1
58 388 1
610 1000 1
388 157 1
1185 1966 1
610 890 1
1966 329 1
1185 800 1
1358 1316 1
890 1517 1
388 1708 1
157 1116 1
157 21 1
1517 1612 1
1612 879 1
1708 567 1
1708 1850 1
1316 124 1
567 5...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 2000 numbers

Test #6:

score: 15
Accepted
time: 31ms
memory: 18164kb

input:

2000 99
117 583 1
117 1553 1
1553 301 1
1553 912 1
912 1582 1
912 1045 1
1582 522 1
1045 898 1
1045 385 1
898 1090 1
385 1499 1
1090 1790 1
1499 1347 1
1499 417 1
1347 1465 1
1465 1932 1
417 291 1
1465 345 1
1932 1312 1
345 1027 1
1027 210 1
1312 1180 1
210 588 1
210 1156 1
1156 1901 1
1901 1662 1
1...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 2000 numbers

Subtask #3:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #7:

score: 15
Accepted
time: 32ms
memory: 18156kb

input:

2000 1451615371
1496 1341 49707670
1341 444 345030850
1496 1007 685475095
444 1909 278749381
1909 1110 3639571
1341 1869 60712733
1869 521 19317650
1007 732 443227891
444 1258 126491905
1496 1004 482872791
1110 1504 31497121
1004 279 30903287
521 1485 375275915
1007 605 72133480
1869 1570 326176977
...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 2000 numbers

Test #8:

score: 15
Accepted
time: 32ms
memory: 17932kb

input:

2000 18850124083
950 1232 22289119
1232 1743 201827311
950 852 235698364
1743 430 879933721
950 416 192976076
1743 195 44313799
950 318 36655137
416 1669 371460821
416 1541 46177715
430 1339 66159023
852 1642 517803961
195 358 294138445
1669 671 183145735
195 1096 412001955
318 1549 213915493
1339 1...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 2000 numbers

Test #9:

score: 15
Accepted
time: 33ms
memory: 20088kb

input:

2000 24843324444
1717 1032 273506143
1717 1999 561959269
1999 1982 29071225
1982 1537 8968261
1982 768 2135953
1982 1125 432656466
1537 1291 56651365
1125 302 269030781
302 1842 161254215
302 138 76677902
138 1663 558013730
1842 1384 269534851
1384 1706 317644801
1663 1240 280572041
1706 628 5688469...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 2000 numbers

Subtask #4:

score: 0
Time Limit Exceeded

Test #10:

score: 0
Time Limit Exceeded

input:

100000 49999
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1
...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #2:

100%
Accepted

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%