题目链接

(Luogu) https://www.luogu.org/problem/P4727

(BZOJ) https://www.lydsy.com/JudgeOnline/problem.php?id=1488

题解

Burnside引理经典题。

首先考虑一个\(O(n!\times poly(n))\)暴力: 枚举点的置换，然后计算在置换下保持不变的图的个数。

把置换拆成若干个轮换。

(1) 考虑轮换内部: 假设一轮换为\((a_1\ a_2\ ...\ a_n)\), 那么\((a_1,a_2),(a_2,a_3),...,(a_n,a_1)\)这些边要么都存在要么都不存在；\((a_1,a_3),(a_2,a_4),...,(a_{n-1},a_{1}),(a_{n},a_2)\)这些边也要么都存在要么都不存在；一般地说，对于任何一个\(d\), 所有的\((a_i,a_{(i+d)\mod n})\)这些边要么都存在要么都不存在，因此轮换内部一共有\(2^{\frac{n}{2}}\)种方案。

(2) 考虑轮换之间: 假设两轮换分别为\((a_1,a_2,...,a_n),(b_1,b_2,...,b_m)\)则有: \((a_1,b_1),(a_2,b_2),...(a_i,b_i)\)这些边存在情况都相同；\((a_1,b_2),(a_2,b_3),...,(a_i,b_{i+1})\)这些边存在情况都相同；以此类推，可以得到两轮换之间共有\(2^{\gcd(n,m)}\)种方案。

所有的置换方案数相加，最后除以置换总数\(n!\).

然后现在考虑\(n\le 60\)怎么办。

当\(n\le 60\)时，我们可以枚举拆分数(\(60\)的拆分数约为百万级别)。

已知一个拆分的方案(方案是指一个无标号序列\(a\)满足\(\sum a_i=n\)，其长度为\(cnt\))，它对应了多少个不同排列的轮换分拆？

首先，长度为\(L\)的轮换共\((L-1)!\)种。

然后我们要处理标号问题。

假设轮换之间是有区别的，那么标号方案数为\(\frac{n!}{\prod^{cnt}_{i=1}a_i!}\).

但是长度相等的轮换之间没有区别，所以除以\(\prod {num_i!}\), 其中\(num_i\)表示\(i\)在\(a\)中的出现次数。

最后乘起来得到\(\frac{n!}{\prod^{cnt}_{i=1}a_i\prod^n_{i=1}num_i!}\)

累加即可。

时间复杂度？

枚举所有拆分方案，求\(cnt^2\)之和，我用程序计算得当\(n=60\)时该值约为\(2.7\times 10^8\).

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<iostream>

#define llong long long

using namespace std;

inline int read()

{

	int x=0; bool f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');

	if(f) return x;

	return -x;

}

const int N = 60;

const int P = 997;

llong fact[N+3],finv[N+3],inv[N+3];

llong pw2[N+3];

int a[N+3];

int num[N+3];

int gcd[N+3][N+3];

int n,cnt;

llong ans;

int GCD(int x,int y)

{

	return y==0?x:GCD(y,x%y);

}

llong quickpow(llong x,llong y)

{

	llong cur = x,ret = 1ll;

	for(int i=0; y; i++)

	{

		if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}

		cur = cur*cur%P;

	}

	return ret;

}

llong calc()

{

	llong ret = fact[n];

	for(int i=1; i<=cnt; i++)

	{

		ret = ret*inv[a[i]]%P;

	}

	for(int i=1; i<=n; i++)

	{

		ret = ret*finv[num[i]]%P;

	}

	for(int i=1; i<=cnt; i++)

	{

		ret = ret*pw2[a[i]>>1]%P;

	}

	for(int i=1; i<=cnt; i++)

	{

		for(int j=i+1; j<=cnt; j++)

		{

			ret = ret*pw2[gcd[a[i]][a[j]]]%P;

		}

	}

	return ret;

}

void dfs(int sum)

{

	if(sum==n)

	{

		ans = (ans+calc())%P;

		return;

	}

	for(int i=a[cnt]; i+sum<=n; i++)

	{

		cnt++; a[cnt] = i; num[i]++;

		dfs(i+sum);

		a[cnt] = 0; cnt--; num[i]--;

	}

}

int main()

{

	pw2[0] = 1ll; for(int i=1; i<=N; i++) pw2[i] = (pw2[i-1]<<1)%P;

	fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;

	finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;

	for(int i=1; i<=N; i++) inv[i] = finv[i]*fact[i-1]%P;

	for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) gcd[i][j] = GCD(i,j);

	scanf("%d",&n);

	if(n==0) {printf("1"); return 0;}

	a[0] = 1; dfs(0);

	ans = ans*finv[n]%P;

	printf("%lld\n",ans);

	return 0;

}