QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#508516 | #7792. Tree Topological Order Counting | DaiRuiChen007 | 0 | 93ms | 16404kb | C++17 | 1.3kb | 2024-08-07 16:42:27 | 2024-08-07 16:42:27 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5005,MOD=1e9+7;
ll ksm(ll a,ll b=MOD-2) {
ll ret=1;
for(;b;a=a*a%MOD,b>>=1) if(b&1) ret=ret*a%MOD;
return ret;
}
vector <int> G[MAXN];
int n,fa[MAXN],siz[MAXN],a[MAXN];
ll fac[MAXN],inv[MAXN],ifac[MAXN],g[MAXN],ig[MAXN],f[MAXN][MAXN],ans[MAXN];
ll C(int x,int y) {
if(x<0||y<0||y>x) return 0;
return fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
void dfs0(int u) {
siz[u]=g[u]=ig[u]=1;
for(int v:G[u]) {
dfs0(v),siz[u]+=siz[v];
g[u]=g[u]*g[v]%MOD;
}
g[u]=g[u]*inv[siz[u]]%MOD;
ig[u]=ig[u]*siz[u]%MOD;
}
void dfs1(int u) {
ans[u]=fac[siz[u]]*g[u]%MOD*f[u][1]%MOD;
for(int v:G[u]) {
ll w=fac[siz[u]-siz[v]-1]*g[u]%MOD*ig[v]%MOD*siz[u]%MOD;
for(int k=2;k<=siz[u];++k) for(int i=max(1,k-siz[u]+siz[v]);i<=siz[v]&&i<k;++i) {
f[v][i]=(f[v][i]+f[u][k]*w%MOD*C(k-2,i-1)%MOD*C(siz[u]-k,siz[v]-i))%MOD;
}
dfs1(v);
}
}
signed main() {
scanf("%d",&n);
for(int i=fac[0]=ifac[0]=1;i<=n;++i) ifac[i]=ksm(fac[i]=fac[i-1]*i%MOD),inv[i]=ksm(i);
for(int i=2;i<=n;++i) scanf("%d",&fa[i]),G[fa[i]].push_back(i);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
dfs0(1);
for(int i=1;i<=n;++i) f[1][i]=a[i];
dfs1(1);
for(int i=1;i<=n;++i) printf("%lld ",ans[i]); puts("");
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: 1ms
memory: 4068kb
input:
10 1 2 2 4 2 5 3 2 3 421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543
output:
132551152 41677919 102495837 551247922 120000529 379839125 398510240 518510769 379839125 518510769
result:
wrong answer 2nd numbers differ - expected: '750202542', found: '41677919'
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: 93ms
memory: 16404kb
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:
16671810 327085511 954611734 991915797 246024471 819506667 440190361 921261170 121769963 977066023 27455643 666529375 479362885 921821860 392703848 766133421 133335504 968612682 199685361 440344548 329645679 508611620 268487003 101941549 378536289 169449008 288736252 783267323 185632991 164728028 24...
result:
wrong answer 2nd numbers differ - expected: '944499931', found: '327085511'
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%