BZOJ 1478 | 1488 | 1815 无标号无向完全有色图计数

给定一个无向完全图,边有颜色,求所有不同构的图的数量。

这里我们考虑所有边的置换,边的置换太大了,发现边的置换和点的置换是有关的,而且点的置换和图的同构是有关的,所以我们枚举所有点的置换。

但是这样是 n! 的复杂度。我们发现对于两个置换,如果对于每一个大小的轮换,他们都具有相同的轮换个数,那么对于答案的贡献就是等价的。

那么我们就可以枚举整数拆分了。复杂度变成点数的拆分数了。

这样我们对于每一置换都求一下对答案的贡献,然后乘一下轮换个数就好了。

轮换个数怎么算呢……首先是根据拆分组合数搞一下

其中 div_num 是拆分数组。

然后考虑假设大小为 x 的轮换有 y 个,那么我们还要除以 y!

然后注意到每个循环排列方式只和第一个点有关,或者说,因为这是个圆排列所以要去重 (除掉 div\_num[i]),所以我们还要挨个乘 (div\_num[i]-1)!

然后后面就是考虑怎么算边的轮换大小了,见这里:

从小学开始的数数

代码:

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据