QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#658829 | #7792. Tree Topological Order Counting | sunkaihuan | 0 | 91ms | 16060kb | C++14 | 1.2kb | 2024-10-19 17:42:37 | 2024-10-19 17:42:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5005,mod=1e9+7;
long long dp[N][N],wl[N];
long long fac[N],inv[N];
int n,sz[N];vector<int> to[N];
long long c(int x,int y){
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
long long iv(long long a){
long long b=mod-2,c=1;
while(b){
if(b&1)c=c*a%mod;a=a*a%mod;b>>=1;
}return c;
}
void init(int x){
wl[x]=sz[x]=1;
for(auto j:to[x])
init(j),wl[x]=wl[x]*wl[j]%mod*iv(sz[j])%mod,sz[x]+=sz[j];
wl[x]=wl[x]*fac[sz[x]-1]%mod;
}
void solve(int x){//cout<<x<<"\n";
long long wx;
for(auto i:to[x]){
wx=wl[x]*iv(c(sz[x]-1,sz[i]))%mod*iv(wl[i])%mod;
for(int j=1;j<=sz[x]-sz[i];j++)
for(int k=0;k<sz[i];k++)
dp[i][k]=(dp[i][k]+wx*dp[x][j+k]%mod*c(j+k-1,k)%mod*c(sz[x]-j-k-1,sz[i]-k-1)%mod)%mod;
solve(i);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0); cin>>n; int x;
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
inv[n]=iv(fac[n]);for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
for(int i=2;i<=n;i++)cin>>x,to[x].push_back(i);
for(int i=1;i<=n;i++)cin>>dp[1][i-1];
init(1);solve(1);long long ans=0;
for(int i=1;i<=n;i++)cout<<dp[i][0]*wl[i]%mod<<" ";
}
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: 3724kb
input:
10 1 2 2 4 2 5 3 2 3 421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543
output:
849644921 665126816 512561637 512561637 666539196 165721184 318062726 492300961 165721184 492300961
result:
wrong answer 1st numbers differ - expected: '132551152', found: '849644921'
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: 91ms
memory: 16060kb
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:
419936127 505241438 976764680 601428284 31809093 826043688 578333698 95009794 665798888 820118594 35072334 85697633 167584868 21511095 872471456 340365279 767528507 959061083 131484299 990194792 442740751 659996386 786035351 162215574 874635769 580933900 169559211 943091866 368901331 866337380 61840...
result:
wrong answer 1st numbers differ - expected: '16671810', found: '419936127'
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%