QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#253795 | #7792. Tree Topological Order Counting | zhouhuanyi | 0 | 121ms | 115764kb | C++14 | 1.6kb | 2023-11-17 15:46:02 | 2023-11-17 15:46:03 |
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]%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][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;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 101724kb
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 961231270 80004754 418552104 586592139 166659690 418552104 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: 121ms
memory: 115764kb
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 571262980 305778430 679771307 446954915 412849015 570179330 701723544 539399739 519330231 599714411 657420361 452018369 2340816 812345757 942564500 528789884 821742180 522429933 809755539 185683511 512279376 763316398 318275496 878605147 850743364 202662616 311900072 250348270 852...
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%