题解 [ARC121E] Directed Tree

Graphcity · 2022-12-03 16:59:30 · 题解

比较简单的二项式反演题。

观察到原题的条件相当于不存在 a_i 是 i 的祖先。考虑二项式反演，设 f_i 为钦定有 i 个点不满足条件的方案数。

再设 f_{x,i} 为 x 子树内钦定了 i 个点不满足条件的方案数。对于结点 x 和它的一个儿子 y，有转移 f_{x,i+j}\gets f_{x,i}\times f_{y,j}。

当然也可以存在子树内的结点连到它自己，有转移 f_{x,i}\gets f_{x,i}+f_{x,i-1}\times (siz_x-i)。

剩下的未被钦定的点随便匹配即可，f_i=f_{1,i}\times (n-i)!。

二项式反演，ans=\sum_{i=0}^n(-1)^if_i。

时间复杂度 O(n^2)。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e3,Mod=998244353;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int n,fa[Maxn+5],siz[Maxn+5],fac[Maxn+5];
int f[Maxn+5][Maxn+5],g[Maxn+5];
vector<int> v[Maxn+5];

inline void dfs(int x)
{
    f[x][0]=1,siz[x]=1;
    for(auto y:v[x]) dfs(y);
    for(auto y:v[x])
    {
        For(i,0,siz[x]+siz[y]) g[i]=0;
        For(i,0,siz[x]) For(j,0,siz[y]) g[i+j]=(g[i+j]+1ll*f[x][i]*f[y][j]%Mod)%Mod;
        For(i,0,siz[x]+siz[y]) f[x][i]=g[i];
        siz[x]+=siz[y];
    }
    Rof(i,siz[x],1) f[x][i]=(f[x][i]+1ll*f[x][i-1]*(siz[x]-(i-1)-1)%Mod)%Mod;
}

int main()
{
    n=read(),fac[0]=1;
    For(i,1,n) fac[i]=1ll*fac[i-1]*i%Mod;
    For(i,2,n) v[fa[i]=read()].push_back(i);
    dfs(1);
    int ans=0;
    For(i,0,n) f[1][i]=1ll*f[1][i]*fac[n-i]%Mod;
    For(i,0,n) ans=(ans+(i&1?-1ll:1ll)*f[1][i])%Mod;
    printf("%d\n",(ans+Mod)%Mod);
    return 0;
}