ARC121E Directed Tree 题解

将对排列

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-i-1)+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;
}

ARC121E Directed Tree 题解

文章操作

相关推荐

评论

ARC121E Directed Tree 题解