QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#320654 | #7792. Tree Topological Order Counting | yyyyxh | 0 | 29ms | 1564kb | C++14 | 968b | 2024-02-03 19:39:35 | 2024-02-03 19:39:36 |
Judging History
answer
#include <cstdio>
using namespace std;
typedef long long ll;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=5003,P=998244353;
int qp(int a,int b=P-2){
int res=1;
while(b){
if(b&1) res=(ll)res*a%P;
a=(ll)a*a%P;b>>=1;
}
return res;
}
int n,f[N],s[N],fac[N];
int dp[N],res[N];
int main(){
n=read();
fac[0]=1;
for(int i=1;i<=n;++i) s[i]=1,fac[i]=(ll)fac[i-1]*i%P;
for(int i=2;i<=n;++i) f[i]=read();
for(int i=n;i>1;--i) s[f[i]]+=s[i];
dp[1]=1;
for(int x=0;x<n;++x){
int p=read();
for(int i=n;i;--i){
res[i]=(res[i]+(ll)dp[i]*fac[n-x-1]%P*p)%P;
dp[i]=((ll)dp[f[i]]*s[f[i]]+(ll)dp[i]*(n-x-s[i]))%P;
}
}
int prod=1;
for(int i=1;i<=n;++i) prod=(ll)prod*s[i]%P;
prod=qp(prod);
for(int i=1;i<=n;++i){
res[i]=(ll)res[i]*prod%P*s[i]%P;
printf("%d ",res[i]);
}
putchar('\n');
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1524kb
input:
10 1 2 2 4 2 5 3 2 3 421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543
output:
791644175 293112286 383600722 383600722 556722198 47472573 200339152 378530675 47472573 378530675
result:
wrong answer 1st numbers differ - expected: '132551152', found: '791644175'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Wrong Answer
Test #22:
score: 0
Wrong Answer
time: 29ms
memory: 1564kb
input:
3000 1 1 3 1 3 6 1 5 3 2 4 9 6 7 2 7 1 1 8 1 4 17 23 2 5 24 15 12 14 28 16 32 33 16 6 1 3 12 17 31 33 19 43 3 33 7 35 42 23 15 30 12 8 21 16 38 53 8 49 56 21 25 30 54 30 14 20 10 35 28 35 55 12 50 10 1 75 76 19 22 8 82 4 68 42 9 57 68 3 67 56 8 11 23 72 68 9 62 32 20 73 39 74 56 88 61 83 78 69 29 29...
output:
110633451 362175117 686253574 917202832 896799598 716598028 592139373 274768793 45891554 658401827 26962073 373827872 289717969 381261928 667880130 250899793 329896034 914035356 573876981 975312576 633570496 571937780 790393251 611814733 704467728 571503924 55239706 389767600 955619048 764968317 698...
result:
wrong answer 1st numbers differ - expected: '16671810', found: '110633451'
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%