QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#658829#7792. Tree Topological Order Countingsunkaihuan0 91ms16060kbC++141.2kb2024-10-19 17:42:372024-10-19 17:42:37

Judging History

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

  • [2024-10-19 17:42:37]
  • 评测
  • 测评结果:0
  • 用时:91ms
  • 内存:16060kb
  • [2024-10-19 17:42:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5005,mod=1e9+7;
long long dp[N][N],wl[N];
long long fac[N],inv[N];
int n,sz[N];vector<int> to[N];

long long c(int x,int y){
	return fac[x]*inv[y]%mod*inv[x-y]%mod; 
}

long long iv(long long a){
	long long b=mod-2,c=1;
	while(b){
		if(b&1)c=c*a%mod;a=a*a%mod;b>>=1; 
	}return c;
}

void init(int x){
	wl[x]=sz[x]=1;
	for(auto j:to[x])
		init(j),wl[x]=wl[x]*wl[j]%mod*iv(sz[j])%mod,sz[x]+=sz[j];
	wl[x]=wl[x]*fac[sz[x]-1]%mod;
}

void solve(int x){//cout<<x<<"\n";
	long long wx;
	for(auto i:to[x]){
		wx=wl[x]*iv(c(sz[x]-1,sz[i]))%mod*iv(wl[i])%mod;
		for(int j=1;j<=sz[x]-sz[i];j++)
			for(int k=0;k<sz[i];k++)
				dp[i][k]=(dp[i][k]+wx*dp[x][j+k]%mod*c(j+k-1,k)%mod*c(sz[x]-j-k-1,sz[i]-k-1)%mod)%mod;
		solve(i);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0); cin>>n; int x;
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	inv[n]=iv(fac[n]);for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
	for(int i=2;i<=n;i++)cin>>x,to[x].push_back(i);
	for(int i=1;i<=n;i++)cin>>dp[1][i-1];
	init(1);solve(1);long long ans=0;
	for(int i=1;i<=n;i++)cout<<dp[i][0]*wl[i]%mod<<" ";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3724kb

input:

10
1 2 2 4 2 5 3 2 3
421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543

output:

849644921 665126816 512561637 512561637 666539196 165721184 318062726 492300961 165721184 492300961 

result:

wrong answer 1st numbers differ - expected: '132551152', found: '849644921'

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: 91ms
memory: 16060kb

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:

419936127 505241438 976764680 601428284 31809093 826043688 578333698 95009794 665798888 820118594 35072334 85697633 167584868 21511095 872471456 340365279 767528507 959061083 131484299 990194792 442740751 659996386 786035351 162215574 874635769 580933900 169559211 943091866 368901331 866337380 61840...

result:

wrong answer 1st numbers differ - expected: '16671810', found: '419936127'

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%