QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253804 | #7792. Tree Topological Order Counting | zhouhuanyi | 0 | 124ms | 175684kb | C++14 | 1.8kb | 2023-11-17 15:58:30 | 2023-11-17 15:58:30 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#define N 5000
#define mod 1000000007
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int MD(int x)
{
return x>=mod?x-mod:x;
}
void Adder(int &x,int d)
{
x+=d;
if (x>=mod) x-=mod;
return;
}
int n,fa[N+1],sz[N+1],C[N+1][N+1],dp[N+1][N+1],rst[N+1][N+1],DP[N+1],ans[N+1],F[N+1];
vector<int>E[N+1];
void dfs(int x)
{
DP[x]=1;
for (int i=0;i<E[x].size();++i) dfs(E[x][i]),DP[x]=1ll*DP[x]*DP[E[x][i]]%mod*C[sz[x]+sz[E[x][i]]][sz[x]]%mod,sz[x]+=sz[E[x][i]];
sz[x]++;
return;
}
void dfs2(int x)
{
int smz=sz[x]-1,dst=0;
ans[x]=dp[x][1];
for (int i=1;i<=smz;++i) dp[x][i]=dp[x][i+1];
rst[x][E[x].size()]=1;
for (int i=E[x].size()-1;i>=0;--i) rst[x][i]=1ll*rst[x][i+1]*C[dst+sz[E[x][i]]][dst]%mod*DP[E[x][i]]%mod,dst+=sz[E[x][i]];
for (int i=0;i<E[x].size();++i)
{
smz-=sz[E[x][i]];
for (int j=1;j<=smz;++j) F[j]=0;
for (int j=1;j<=smz;++j)
for (int k=0;k<=sz[E[x][i]];++k)
Adder(F[j],1ll*C[j-1+k][j-1]*C[smz-j+sz[E[x][i]]-k][smz-j]%mod*dp[x][j+k]%mod);
for (int j=1;j<=sz[E[x][i]];++j)
for (int k=0;k<=smz;++k)
Adder(dp[E[x][i]][j],1ll*C[j-1+k][j-1]*C[sz[E[x][i]]-j+smz-k][sz[E[x][i]]-j]%mod*dp[x][j+k]%mod*rst[x][i+1]%mod);
for (int j=1;j<=smz;++j) dp[x][j]=F[j];
dfs2(E[x][i]);
}
return;
}
int main()
{
int x;
for (int i=0;i<=N;++i) C[i][0]=1;
for (int i=1;i<=N;++i)
for (int j=1;j<=i;++j)
C[i][j]=MD(C[i-1][j-1]+C[i-1][j]);
n=read();
for (int i=2;i<=n;++i) x=read(),E[x].push_back(i);
for (int i=1;i<=n;++i) dp[1][i]=read();
dfs(1),dfs2(1);
for (int i=1;i<=n;++i) printf("%lld ",1ll*ans[i]*DP[i]%mod);
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: 3ms
memory: 106536kb
input:
10 1 2 2 4 2 5 3 2 3 421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543
output:
132551152 750202542 844925059 922462533 160009508 418552104 173184271 333193779 418552104 333193779
result:
wrong answer 4th numbers differ - expected: '844925059', found: '922462533'
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: 124ms
memory: 175684kb
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 944499931 899918400 565889769 867105142 859081650 270558026 140049597 245677528 674200242 336880452 672888050 139150927 585351650 820283667 921699486 350289810 23859761 217994310 770817134 819874676 673540793 668114841 863122831 994151974 640249332 965394761 899844687 70055127 135979889 114...
result:
wrong answer 3rd numbers differ - expected: '273506025', found: '899918400'
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%