[洛谷P4727][HNOI2009]图的同构记数

这是一个比较傻逼的Polya计数的题,但是我想了很长时间,说明我太菜了。
考虑Burnside定理,枚举每一个置换,然后计算不动点个数。不动点个数就是原先两点之间的连边状态和置换后两点之间的连边状态相同的图的个数。我们可以发现循环节内部的连边方案数和循环节两两之间连边的方案数都分别独立,所以我们可以分开来计算。对于一个大小为x的循环节,其内部连边方案显然为$2^{\lfloor \frac{x}{2} \rfloor}$。对于大小为x的循环节和大小为y的循环节之间的连边方案仔细想一下就会发现是$2^{gcd(x,y)}$。
那么假设第i个循环节为$a_i$,那么答案就是$\displaystyle\prod_{i=1}^m 2^{\lfloor \frac{a_i}{2} \rfloor } \displaystyle\prod_{j=i+1}^m 2^{gcd(a_i,a_j)}$。既然答案只和这些东西有关,那么直接枚举划分然后计算方案即可(具体做法和PE495类似)。然后这道题就做完了。
我发现我有一个问题没想清楚,就是为什么这个可以用Burnside定理。我看了题解才知道这个东西相当于对边黑白染色,说明我太菜了。

Tagged with:

发表评论