[HNOI2009]图的同构记数

题意

在所以置换下，本质不同的\(n\)阶图个数

做法

可以假想成\(K_n\)，边有黑白两色，黑边存在于原图，白边存在于补图
由于\(n\le 60\)，可以手算出拆分数不大，所以我们爆搜置换群

对于一个拆分方案（置换的分解序列）\((a_1,a_2,...,a_k)(a_1\le a_2\le ...\le a_k)\)

考虑某个因子内的黑边\((m=|a_i|)\)，如果\((1,2)\)为黑边，则\((2,3),(3,4),...,(m,1)\)均为黑边
依次可推得有\(\left\lfloor\frac{m}{2}\right\rfloor\)个等价类（并不是\(m-1\)个，可以手玩一下）
考虑两个因子件的黑边\((m_1=|a_i|,m_2=|a_j|,i\neq j)\)，有\((m_1,m_2)\)个等价类

当然，对于一个拆分方案\((a_1,a_2,...,a_k)\)（以下\(num_i\)为\(i\)在其中出现的次数）
于置换显然不是双射关系，还得对应到若干个置换中去，统计置换个数（这部分网上有些题解有问题）：
\[\frac{n!}{\prod\limits_{i=1}^k (a_i!)}\times \prod\limits_{i=1}^k ((a_i-1)!)\times\prod\limits_{i=1}^n \frac{1}{num_i!}=\frac{n!}{\prod\limits_{i=1}^k (a_i)\prod\limits_{i=1}^n (num_i!)}\]

巴特西

[HNOI2009]图的同构记数

题意

做法

最新文章

热门文章