QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#729290#9566. Topologyucup-team5319#WA 1ms7720kbC++141.5kb2024-11-09 16:50:462024-11-09 16:50:47

Judging History

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

  • [2024-11-09 16:50:47]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7720kb
  • [2024-11-09 16:50:46]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5000+10,MOD=1e9+7;
int n,sze[MAXN],b[MAXN],frac[MAXN],inv[MAXN],tcnt[MAXN];
vector<int> G[MAXN];
int qpow(int base,int p) {
	int ans=1;
	while(p) {
		if(p&1) ans=ans*base%MOD;
		base=base*base%MOD,p>>=1;
	}
	return ans;
}
void dfs1(int u) {
	tcnt[u]=1,sze[u]=1;
	for(auto v:G[u]) dfs1(v),sze[u]+=sze[v],tcnt[u]=tcnt[u]*tcnt[v]%MOD*inv[sze[v]]%MOD;
	tcnt[u]=tcnt[u]*frac[sze[u]-1]%MOD;
	return ;
}
int dp[MAXN][MAXN];
int C(int u,int d) {
	return frac[d]*inv[u]%MOD*inv[d-u]%MOD;	
}
void dfs2(int u) {
	int mul=1;
	for(auto v:G[u]) mul=mul*tcnt[v]%MOD*inv[sze[v]]%MOD;
	for(auto v:G[u]) {
		int insv=qpow(tcnt[v]*inv[sze[v]]%MOD,MOD-2);
		ffor(r,1,n-sze[u]+1) dp[v][r+1]=(dp[v][r+1]+dp[u][r]*mul%MOD*insv%MOD*frac[sze[u]-sze[v]-1]%MOD*C(sze[u]-sze[v]-1,n-sze[u]+1-r+sze[u]-sze[v]-1))%MOD;	
	}
	for(auto v:G[u]) ffor(r,1,n-sze[v]+1) dp[v][r]=(dp[v][r]+dp[v][r-1])%MOD;
	for(auto v:G[u]) dfs2(v);
	return ;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n,frac[0]=1;
	ffor(i,1,n) frac[i]=frac[i-1]*i%MOD;
	inv[n]=qpow(frac[n],MOD-2);
	roff(i,n-1,0) inv[i]=inv[i+1]*(i+1)%MOD;
	ffor(i,2,n) {int f;cin>>f,G[f].push_back(i);}
	dfs1(1);
	dp[1][1]=1;
	dfs2(1);
	ffor(i,1,n) {
		int ans=0;
		ffor(j,1,n-sze[i]+1) {
			int cnt=dp[i][j]*tcnt[i]%MOD*C(sze[i]-1,n-j)%MOD;
			if(i==j) ans=(ans+cnt)%MOD;
		}
		cout<<ans<<' ';
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5700kb

input:

4
1 1 2

output:

3 2 1 2 

result:

ok 4 number(s): "3 2 1 2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5760kb

input:

9
1 1 2 2 3 3 4 5

output:

672 420 180 160 152 108 120 170 210 

result:

ok 9 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

2
1

output:

1 1 

result:

ok 2 number(s): "1 1"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 7720kb

input:

500
1 2 3 4 5 6 7 7 8 10 8 10 11 4 11 12 12 17 15 13 21 21 22 5 16 9 24 28 28 19 29 27 17 33 23 3 33 27 30 9 25 34 16 26 30 34 46 45 41 14 43 49 43 35 39 37 26 48 52 58 51 56 51 55 19 48 63 36 67 69 54 60 71 61 29 40 32 77 73 55 66 42 77 72 71 69 62 83 46 64 88 39 83 36 89 94 47 98 57 61 38 80 78 88...

output:

704037249 704037249 792984966 949305280 328467754 938524453 999244921 541069063 876302362 83238210 762280537 336088991 137489850 623012453 595945369 535922071 856668610 236678618 211816261 404754874 518308767 386536911 620951794 627611753 805834361 677494497 350991736 707605568 772719797 721492374 1...

result:

wrong answer 1st numbers differ - expected: '331058271', found: '704037249'