QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#782690 | #9566. Topology | Ludovica | WA | 1ms | 5904kb | C++14 | 1.6kb | 2024-11-25 21:00:39 | 2024-11-25 21:00:40 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=5010,M=4e5+10;
const int INF=1e18;
const int mod=998244353;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,fac[N],invfac[N],siz[N],mul[N],f[N],dp[N][N];
vector<int> adj[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]=1;
for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
invfac[n]=qpow(fac[n],mod-2);
for(int i=n-1;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%mod;
}
int C(int n,int m){
if(n<m)return 0;
return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
void dfs(int u){
siz[u]=f[u]=mul[u]=1;
for(auto v:adj[u]){
dfs(v);
siz[u]+=siz[v];
mul[u]=mul[u]*mul[v]%mod;
}
mul[u]=mul[u]*siz[u]%mod;
f[u]=fac[siz[u]]*qpow(mul[u],mod-2)%mod;
}
void dfs1(int u){
for(auto v:adj[u]){
int tmp=f[u]*mul[v]%mod*siz[u]%mod*qpow(siz[u]-siz[v],mod-2)%mod*invfac[siz[u]]%mod*fac[siz[u]-siz[v]]%mod;
for(int i=1;i<=n;i++){
dp[v][i]=dp[u][i-1]*tmp%mod*C(n-i+1-siz[v],siz[u]-siz[v]-1)%mod;
dp[v][i]+=dp[v][i-1];
dp[v][i]%=mod;
}
dfs1(v);
}
}
void solve(){
cin>>n;
init();
for(int i=2;i<=n;i++){
int x;
cin>>x;
adj[x].push_back(i);
}
dp[1][1]=1;
dfs(1);
dfs1(1);
for(int i=1;i<=n;i++){
dp[i][i]=dp[i][i]*f[i]%mod*C(n-i,siz[i]-1)%mod;
cout<<dp[i][i]<<" \n"[i==n];
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int T;
cin>>T;
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5904kb
input:
4 1 1 2
output:
1 1 1 0 1 0
result:
wrong answer 1st numbers differ - expected: '3', found: '1'