QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#714414 | #9566. Topology | ucup-team1196 | TL | 0ms | 3624kb | C++23 | 2.0kb | 2024-11-05 23:07:04 | 2024-11-05 23:07:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2009,mod=998244353;
int fac[N],invfac[N];
int qpow(int a,int b){
int ans=1;
for(;b;b>>=1){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
}
return ans;
}
void init(){
fac[0]=invfac[0]=1;
for(int i=1;i<=N-8;++i) fac[i]=fac[i-1]*i%mod;
invfac[N-8]=qpow(fac[N-8],mod-2);
for(int i=N-8;i;--i) invfac[i-1]=invfac[i]*i%mod;
}
int C(int x,int y){
if(x<y) return 0;
return fac[x]*invfac[x-y]%mod*invfac[y]%mod;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
init();
int n;
cin>>n;
vector<vector<int>>e(n+1);
for(int i=2;i<=n;++i){
int x;
cin>>x;
e[x].push_back(i);
}
vector<int>sz(n+1),f(n+1),dep(n+1);
vector g(n+1,vector(n+1,0ll));
dep[1]=1;
auto dfs=[&](auto dfs,int u)->void{
sz[u]=1;
f[u]=1;
for(auto v:e[u]){
dep[v]=dep[u]+1;
dfs(dfs,v);
sz[u]+=sz[v];
f[u]=f[u]*f[v]%mod*invfac[sz[v]]%mod;
}
f[u]=f[u]*fac[sz[u]-1]%mod;
};
dfs(dfs,1);
g[1][1]=1;
auto dfs2=[&](auto dfs2,int u)->void{
int sf=1,sfac=1;
for(auto v:e[u]){
sf=sf*f[v]%mod;
sfac=sfac*invfac[sz[v]]%mod;
}
for(auto v:e[u]){
for(int i=dep[u];i<=n-sz[u]+1;++i){
for(int j=i+1;j<=n-sz[v]+1;++j){
int ans=g[u][i]*C(n-i-sz[v],sz[u]-sz[v]-1)%mod;
ans=ans*sf%mod*qpow(f[v],mod-2)%mod;
ans=ans*sfac%mod*fac[sz[v]]%mod*fac[sz[u]-1-sz[v]]%mod;
g[v][j]+=ans;
if(g[v][j]>=mod) g[v][j]-=mod;
}
}
dfs2(dfs2,v);
}
};
dfs2(dfs2,1);
for(int i=1;i<=n;++i) cout<<f[i]*g[i][i]%mod*C(n-i,sz[i]-1)%mod<<" \n"[i==n];
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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: 3584kb
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: 3516kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Time Limit Exceeded
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...