学网站建设专业前景,网站营销话术,wordpress仿微信公众号,做我的狗漫画网站P6295 有标号 DAG 计数
https://www.luogu.com.cn/problem/P6295 求解n个点的有标号弱联通DAG个数
首先根据exp的组合意义#xff0c;我们考虑指数型生成函数#xff0c;那么我们先求出不要求弱联通的个数#xff0c;然后ln回去就是弱联通的DAG个数。
然后考虑进行dp我们考虑指数型生成函数那么我们先求出不要求弱联通的个数然后ln回去就是弱联通的DAG个数。
然后考虑进行dp枚举入度为0的点的个数然后得到一个递推式但是实际上这里的枚举相当于是钦定所以我们需要进行二项式反演。
于是最后得到的式子指数上有一个乘法我们可以通过组合数变换变成加法于是这样就可以得到一个可以分治fft的形式但是实际上我们通过生成函数可以直接求解。
