P6295 有標號 DAG 計數

https://www.luogu.com.cn/problem/P6295
求解n個點的有標號弱聯通DAG個數

首先根據exp的組合意義，我們考慮指數型生成函數，那么我們先求出不要求弱聯通的個數，然后ln回去就是弱聯通的DAG個數。

然后考慮進行dp，枚舉入度為0的點的個數，然后得到一個遞推式，但是實際上這里的枚舉相當于是欽定，所以我們需要進行二項式反演。

于是最后得到的式子指數上有一個乘法，我們可以通過組合數變換變成加法，于是這樣就可以得到一個可以分治fft的形式，但是實際上我們通過生成函數可以直接求解。

總結

以上是生活随笔為你收集整理的P6295 有标号 DAG 计数(多项式指数函数对数函数/二项式反演/动态规划/生成函数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。