题目只给一个数字n(1 <= n <= 16).对于所有有n个点,任意两点之间有边,每条边边权为1或2,最小生成树是一条链的图,求它们所有最小生成树的数量之和Mod 1e9+7.
思路心路历程:
乍一眼看去以为是数学题,因为要统计个数,于是开始往并不熟练的排列组合上凑,手膜了几组,然而没有什么收获. 真的当图论去做感觉不大对劲,只能打表不然超时.最后还是看了某999.08分大佬的代码才勉强凑合着做出来. 那位大佬的思路是用一个二进制数status表示某一条链的情况,0表示这条树边权是11表示这条树边权是2,然后根据这个status可以把必须为2的边找出来,即如果有某条树边为2,那么能够覆盖他(连成的环上有他)的边都必须为2.把这些必须为2的边找出来之后,其余的非树边都是可以为1也可以为2的,并不会影响生成树的情况,所以一旦有这样的一条非树边,就把这个状态的total情况*2,最后因为一条链可以有 n!/2 n ! / 2 个排列,所以 tot∗n!/2 t o t ∗ n ! / 2 ,然后把每一个状态的tot累加,得到答案.类似状压dp的表示方法,由此可以得到启示,状态压缩不一定要用在dp里,其他数据范围小的题也是可以用于表示的.