题目链接：bzoj1488 题目大意： 求两两互不同构的含n个点的简单图有多少种。 简单图是关联一对顶点的无向边不多于一条的不含自环的图。 a图与b图被认为是同构的是指a图的顶点经过一定的重新标号以后，a图的顶点集和边集能完全与b图一一对应。 题解： 置换-ploya 把一条边选和不选看成把一条边染成两种颜色之后，就跟bzoj1478/1815一样了..这样看来就是三倍经验了。 #

首先可以把问题转化成在完全图上对边进行黑白染色。 对于每个点的置换，要求出有多少关于边的不动点。把置换分解成循环，可以发现，一个长度为 x x的点的循环内部有⌊x2⌋\lfloor\frac x2\rfloor个边的循环，两个长度为 x x和yy的点的循环之间有 gcd(x,y) \gcd(x,y)个边的循环，这样关于边的不动点总数就是 2m 2^m，其中 m m表示边的循环的总数。 但是直接