bzoj4766 文艺计算姬(完全二分图生成树计数)和一个拓展结论
2022/7/2 23:24:58
本文主要是介绍bzoj4766 文艺计算姬(完全二分图生成树计数)和一个拓展结论,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A点集有\(n\)个点,B点集有\(m\)个点
考虑一棵生成树的prufer序列生成过程,最后剩下的两个点一定是一个在A点集,一个在B点集,也就是说\(n-1\)个A点集的点要被删去,\(m-1\)个B点集的点要被删去,prufer序列中要有\(n-1\)个B点集的点,\(m-1\)个A点集的点。
考虑对于一个长度为\(m-1\)的A点集中点的序列,和一个长度为\(n-1\)的B点集中点的序列,如何归并成一个点集内部没有边的合法prufer序列?考虑prufer序列的过程,每次要将prufer序列当前第一个点和未出现点集中标号最小的点连一条边,那么每次连边时,这个未出现点集中标号最小的点是固定的,要选择他另外一边的点集对应序列的最靠前的点加入prufer序列。而最后未出现点集中剩余的两个点正好就是最后留下的两个点,一定合法。
所以每一对这样的合法序列唯一对应一个合法的prufer序列,所以合法的生成树个数就是\(n^{m-1}m^{n-1}\)
另外一个例子:\(n\)个点的有标号无向图,定义两个图本质不同为存在一对点\((x,y)\),在一个图中点双联通,在另外一个图中不点双联通,求本质不同的无向图个数。
转化为\(n\)个圆点,圆点有标号,方点无标号的圆方树计数。
由于和方点有边的点都是圆点,所以不存在等效的方点,所以可以先算所有点都有标号的个数,再除以方点个数的阶乘。
圆点和方点自然符合二分图染色,可以看作是左侧\(n\)个点,右侧有一些方点,这样一个完全二分图的生成树个数计数。设有\(m\)个点双。
考虑到还有限制方点不可以是叶子,那么在prufer序列中,每个右侧点至少出现一次。那么右侧点这部分prufer序列的要求相当于是有\(n-1\)个位置,每个位置放一个方点,每个方点至少放一次,方点无序,位置有序。这就是第二类斯特林数的定义。所以有\(m\)个方点的情况,答案是\(n^{m-1}\begin{Bmatrix}n-1\\m\end{Bmatrix}\)。所以这个题答案就是
这篇关于bzoj4766 文艺计算姬(完全二分图生成树计数)和一个拓展结论的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南