QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#253804#7792. Tree Topological Order Countingzhouhuanyi0 124ms175684kbC++141.8kb2023-11-17 15:58:302023-11-17 15:58:30

Judging History

你现在查看的是最新测评结果

  • [2023-11-17 15:58:30]
  • 评测
  • 测评结果:0
  • 用时:124ms
  • 内存:175684kb
  • [2023-11-17 15:58:30]
  • 提交

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;
}

详细

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%