QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#729290 | #9566. Topology | ucup-team5319# | WA | 1ms | 7720kb | C++14 | 1.5kb | 2024-11-09 16:50:46 | 2024-11-09 16:50:47 |
Judging History
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'