P6295 有标号 DAG 计数

https://www.luogu.com.cn/problem/P6295
求解n个点的有标号弱联通DAG个数

首先根据exp的组合意义，我们考虑指数型生成函数，那么我们先求出不要求弱联通的个数，然后ln回去就是弱联通的DAG个数。

然后考虑进行dp，枚举入度为0的点的个数，然后得到一个递推式，但是实际上这里的枚举相当于是钦定，所以我们需要进行二项式反演。

于是最后得到的式子指数上有一个乘法，我们可以通过组合数变换变成加法，于是这样就可以得到一个可以分治fft的形式，但是实际上我们通过生成函数可以直接求解。

总结

以上是生活随笔为你收集整理的P6295 有标号 DAG 计数(多项式指数函数对数函数/二项式反演/动态规划/生成函数）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。