[HNOI2009]图的同构记数

题意

求本质不同的\(n\)阶图

做法

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

对于一个拆分方案（置换的分解序列）\((a_1,a_2,...,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)\)，于置换显然不是双射关系，还得对应到若干个置换中去，统计置换个数：
这里的\(a\)序列其实就是可重集合，故为\[\frac{n}{\prod\limits_{i=1}^k (a_i!)}\]

因为我们发现拆分序列是有序的，所以统计这个（\(num_i\)表示在序列中出现的次数）\[\frac{n}{(\prod\limits_{i=1}^k (a_i!))(\prod\limits_{i=1}^n (num_i!))}\]

[HNOI2009]图的同构记数

原文：https://www.cnblogs.com/Grice/p/12267975.html