QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253793 | #7792. Tree Topological Order Counting | zhouhuanyi | 0 | 103ms | 84168kb | C++14 | 1.6kb | 2023-11-17 15:45:16 | 2023-11-17 15:45:17 |
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],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;
ans[x]=dp[x][1];
for (int i=1;i<=smz;++i) dp[x][i]=dp[x][i+1];
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][sz[E[x][i]]-k]%mod*dp[x][j+k]);
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][smz-k]%mod*dp[x][j+k]%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: 72144kb
input:
10 1 2 2 4 2 5 3 2 3 421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543
output:
132551152 750202542 192246254 478948194 137328873 -56734194 298621649 166659690 -56734194 166659690
result:
wrong answer 3rd numbers differ - expected: '844925059', found: '192246254'
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: 103ms
memory: 84168kb
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 737231080 -564732899 612261875 11438134 648531101 5678096 -499945925 171791428 -51348635 519330231 -394998721 6420351 178874866 248436135 586277180 463042522 500422111 -870634375 -592293485 1728949 -95792132 227705253 -377666917 286151997 181925583 -389313097 -713455002 -345811168 -13463489...
result:
wrong answer 2nd numbers differ - expected: '944499931', found: '737231080'
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%