ARC121E Directed Tree 题解

Coffee_zzz · 2025-10-27 11:49:56 · 题解

将对排列 a 的计数转化为对其逆排列 b 的计数，那么此时要求结点 b_i 不在结点 i 的子树内。

考虑容斥。设 g_i 表示钦定 i 个结点不合法，且只考虑这 i 个结点的方案数，那么 ans=\sum\limits_{i=0}^n (-1)^i\times g_i\times (n-i)!。

接下来思考如何求 g_i。设 f_{u,i} 表示以 u 为根的子树内，钦定了 i 个结点不合法，且只考虑这 i 个结点的方案数。考虑转移：

• 新加入一个儿子时，因为两个子树的不合法的集合是不交的，所以可以直接合并，转移方程为 f'_{u,i+j}\leftarrow f_{u,i} \times f_{v,j}；
• 加入所有儿子后，枚举点 u 是否合法，得到转移方程为 f'_{u,i+1} \leftarrow f_{u,i} \times (siz_u-1-i)+f_{u,i+1}。

于是 g_i 就等于 f_{1,i}。时间复杂度 \mathcal O(n^2)。

const int N=2005,mod=998244353;
int n,p[N],siz[N],f[N][N],tmp[N],fac[N],ans;
vector <int> ve[N];
void add(int &u,int v){
    u+=v;
    if(u>=mod) u-=mod;
}
void dfs(int u){
    f[u][0]=1;
    for(auto v:ve[u]){
        dfs(v);
        for(int i=0;i<=siz[u];i++) tmp[i]=f[u][i],f[u][i]=0;
        for(int i=0;i<=siz[u];i++) for(int j=0;j<=siz[v];j++) add(f[u][i+j],1ll*tmp[i]*f[v][j]%mod);
        siz[u]+=siz[v];
    }
    siz[u]++;
    for(int i=siz[u]-1;i>=0;i--) add(f[u][i+1],1ll*f[u][i]*(siz[u]-i-1)%mod);
}
void solve(){
    cin>>n;
    for(int i=2;i<=n;i++) cin>>p[i],ve[p[i]].pb(i);
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    dfs(1);
    for(int i=0;i<=n;i++){
        if(i&1) add(ans,mod-1ll*f[1][i]*fac[n-i]%mod);
        else add(ans,1ll*f[1][i]*fac[n-i]%mod);
    }
    cout<<ans<<endl;
}