Description
求两两互不同构的含n个点的简单图有多少种。
简单图是关联一对顶点的无向边不多于一条的不含自环的图。
a图与b图被认为是同构的是指a图的顶点经过一定的重新标号以后，a图的顶点集和边集能完全与b图一一对应。
Input
输入一行一个整数N，表示图的顶点数，0<=N<=60
Output
输出一行一个整数表示含N个点的图在同构意义下互不同构的图的数目，答案对997取模。
(\)
根据Burnside引理，答案就是所有置换下不动元的平均数(人话)。一个置换可以理解为一种排列，所以置换总数就是(n!)。
然后考虑求出所有的不动元。
首先，假设我们已近得到了(m)个循环节，他们的长度分别为(L_1,L_2...L_m)((L_1+L_2+...+L_m=n))。
然后连边的时候我们分两种情况：
- 边的两端在同一循环节内。
- 边的两端不在同一循环节内。
情况1：
我们设有循环节的大小为(n)。则有(2^{lfloor frac{n}{2} floor})种。
这个可以画图感受一下：我们先把点按(1)到(n)重标号，假设有边((1,k))，那么一定有边((2,2+k-1),(3,3+k-1)...(n,k-1))(因为)。然后(k>2^{lfloor frac{n}{2} floor})情况一定与(k-2^{lfloor frac{n}{2} floor})等价。所以等价类有(lfloor frac{n}{2} floor)个。
情况2：
我们设两个循环节大小分别为(n,m)。则有(2^{gcd(n,m)})种。
我们又来感受一下：我们假设存在边((1,i))，则必有边((2,i+1),(3,i+2)...)如果想让这个循环回到((1,i))，那么至少要有(lcm(n,m))条边，所以等价类有(frac{nm}{lcm(n,m)}=gcd(n,m))种。
然后我们得到了循环节为((L_1,L_2...L_m))的图的情况数，我们还需要得到循环节为((L_1,L_2...L_m))的(n)阶置换有多少种。
种数是(frac{n!}{Pi B_i Pi Li})(其中(B_i)表示长度为(i)的循环节数量)。
首先我们不妨设((L_1leq L_2leq...leq L_m))。然后我们按照(1)到(m)的顺序将得到的一个(1)到(n)的排列划分。这样就有(n!)个序列。
长度相同的循环节的排列会算重：比如((1,2)(3,4))与((3,4)(1,2))应该算作一种(这里((1,2))仅仅表示(1,2)在一个循环中)。所以要除以(Pi B_i)。
同一循环内也会算重：比如((1,2,3))与((2,3,1))算作一种(这里的((1,2,3))表示的是((egin{matrix} 1 2 3\ 2 3 1end{matrix})))。所以要除以(Pi Li)。
然后就完了。
代码：
#include<bits/stdc++.h>
#define ll int
#define mod 997
#define N 65
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n;
int ksm(int t,int x) {
ll ans=1;
for(;x;x>>=1,t=t*t%mod)
if(x&1) ans=ans*t%mod;
return ans;
}
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
int g[N][N];
int f[N],fac[N],inv[mod+5];
int ans;
int num[N];
int cnt;
int pw2[100005];
void dfs(int v,int res) {
if(!res) {
int now=fac[n];
int mi=0;
for(int i=v+1;i<=n;i++) {
now=now*inv[fac[num[i]]*ksm(i,num[i])%mod]%mod;
mi+=i/2*num[i];
for(int j=i+1;j<=n;j++) {
mi+=g[i][j]*num[i]*num[j];
}
mi+=i*num[i]*(num[i]-1)/2;
}
now=now*pw2[mi%(mod-1)]%mod;
(ans+=now)%=mod;
return ;
}
if(!v) return ;
num[v]=0;
dfs(v-1,res);
for(int i=1;i*v<=res;i++) {
num[v]=i;
dfs(v-1,res-i*v);
num[v]=0;
}
}
int main() {
n=Get();
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
pw2[0]=1;
for(int i=1;i<=100000;i++) pw2[i]=(pw2[i-1]<<1)%mod;
inv[0]=inv[1]=1;
for(int i=2;i<=mod;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
for(int i=1;i<=n;i++) {
for(int j=i;j<=n;j++) {
g[i][j]=gcd(i,j);
}
}
dfs(n,n);
cout<<ans*ksm(fac[n],mod-2)%mod;
return 0;
}