QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#766836#9566. TopologyStelorCompile Error//C++202.5kb2024-11-20 18:50:082024-11-20 18:50:09

Judging History

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

  • [2024-11-20 18:50:09]
  • 评测
  • [2024-11-20 18:50:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=998244353;
const int N=5010;
int n,sz[N];
ll C[N][N],dp[N][N],pre[N][N],fac[N],f[N],prod[N];
vector<int> v[N];
bool vis[N];
ll qui(ll a,ll b, ll c){
    ll ret=1;
    while(b){
        if(b&1) ret=ret*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ret;
}
ll inv(ll a){
    return qui(a,mod-2,mod);
}
void init()
{
    fac[0]=1;
    for(int i=1;i<N;++i) fac[i]=fac[i-1]*i%mod;
    C[0][0]=1;
    for(int i=1;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            if(!j) C[i][0]=1;
            if(j>i) break;
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
}
void initDfs(int u,int fa){
    sz[u]=1;
    for(auto j:v[u]){
        if(j==fa) continue;
        initDfs(j,u);
        sz[u]+=sz[j];
    }
}
void initDfs2(int u,int fa){
    ll tmp=1;
    f[u]=1;
    for(auto j:v[u]){
        if(j==fa) continue;
        tmp=tmp*fac[sz[j]]%mod;
    }
    f[u]=f[u]*fac[sz[u]-1]%mod*inv(tmp)%mod;
    for(auto j:v[u]){
        if(j==fa) continue;
        initDfs2(j,u);
        f[u]=f[u]*f[j]%mod;
    }
}
void initDfs3(int u,int fa){
    prod[u]=sz[u];
    for(auto j:v[u]){
        if(j==fa) continue;
        initDfs3(j,u);
    }
    for(auto j:v[u]){
    	if(j==fa) continue;
    	prod[u]=prod[u]*prod[j]%mod;
    }
}
void dfs(int fa,int lll){
    vis[fa]=true;
    ll t1=1;
    for(auto u:v[fa]){
        if(u==lll) continue;
        t1=t1*f[u]%mod;
        t1=t1*inv(fac[sz[u]])%mod;
    }
    for(auto u:v[fa]){
        if(vis[u]) continue;
        ll t2=fac[sz[fa]-sz[u]-1];
        vector<ll> pre(n+1);
        for(int i=1;i<=n;++i){
            if(n-i-sz[u]>=0&&sz[fa]-sz[u]-1>=0)
            pre[i]=dp[fa][i]*C[n-i-sz[u]][sz[fa]-sz[u]-1]%mod;
        }
        for(int i=1;i<=n;++i){
            pre[i]=pre[i-1]+pre[i];
            pre[i]%=mod;
        }
        for(int i=1;i<=n;++i){
            dp[u][i]=pre[i-1]*t1%mod*t2%mod*inv(f[u])%mod*fac[sz[u]]%mod
        }
        dfs(u,fa);
    }
}
void solve(){
    cin >> n;
    for(int i=2;i<=n;++i){
        int x;
        cin >> x;
        v[x].push_back(i);
    }
    init();
    initDfs(1,0);
    initDfs2(1,0);
    initDfs3(1,0);
    dp[1][1]=1;
    dfs(1,0);
    for(int i=1;i<=n;++i){
        ll ans=dp[i][i]*f[i]%mod*C[n-i][sz[i]-1]%mod;
        cout<<ans<<" ";
    }

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Details

answer.code: In function ‘void dfs(int, int)’:
answer.code:91:73: error: expected ‘;’ before ‘}’ token
   91 |             dp[u][i]=pre[i-1]*t1%mod*t2%mod*inv(f[u])%mod*fac[sz[u]]%mod
      |                                                                         ^
      |                                                                         ;
   92 |         }
      |         ~