带标号的DAG的计数方法

网上很多博客都提到了王迪的论文《浅谈容斥原理》(2013年国家集训队论文)
作为一个CDQZ的人,向大家安利一下。

 

问题:求n个点带标号的DAG的个数。答案对取模。

 

容斥原理(反演)的一般形式

对于两个关于集合的函数,如果有

那么我们可以得到

换成也是一样的。

 

Solution

首先有一个比较显然的DP做法。

首先,的特点是没有环,有出度为的点。

为了方便表述,以下”度数“均指”出度“

我们用表示个点的DAG,有个度数为的点的方案数。

那么有

解释一下这个式子。

我们表示先选出个度数为的点。然后我们再枚举删除这个点后剩下的图中度数为的点的个数为,由于比有度数为的点,所以。然后我们考虑如何连边。首先,那个点只能和选出来的个点连边,并且至少连一条边。所以是而不是。然后再考虑剩下的图中除了这个点之外的点和个度数为的点连边,可以随便连,所以是然后乘上剩下的点内部的答案。

这样就有一个做法了。显然是无法通过此题的。

 

现在我们考虑重新定义状态,用容斥原理解决。

我们用表示个点的DAG,恰好是集合中的点出度为

表示个点的DAG,至少有集合中的点出度为

显然有,又容斥原理可以得到

 

显然,答案是,我们可以发现有

并且显然有

带入容斥原理的式子可以得到

现在一共有个状态,为

每个状态的转移是的。

于是我们得到了一个的做法,完美地解决了此题。