QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#253795#7792. Tree Topological Order Countingzhouhuanyi0 121ms115764kbC++141.6kb2023-11-17 15:46:022023-11-17 15:46:03

Judging History

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

  • [2023-11-17 15:46:03]
  • 评测
  • 测评结果:0
  • 用时:121ms
  • 内存:115764kb
  • [2023-11-17 15:46:02]
  • 提交

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%