QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253793#7792. Tree Topological Order Countingzhouhuanyi0 103ms84168kbC++141.6kb2023-11-17 15:45:162023-11-17 15:45:17

Judging History

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

  • [2023-11-17 15:45:17]
  • 评测
  • 测评结果:0
  • 用时:103ms
  • 内存:84168kb
  • [2023-11-17 15:45:16]
  • 提交

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%