[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!)} \]

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