题目链接
将边是否存在问题转化为黑白染色问题。
设置换群为(S)，显然，(|S|=n!)，考虑一个置换会产生多少边的循环。
设一个置换划分为(k)个循环，分别为(A_1,A_2, cdots A_k)。
在点循环(A_i)中，以距离划分，共有(frac{|A_i|}{2})种边，对(ans)的贡献为(2^{frac{|A_i|}{2}})。
对于点循环(A_i,A_j)，若((i,j))有边相连，则构成长度为(lcm(|A_i|,|A_j|))的边循环，共有(frac{|A_i||A_j|}{lcm(|A_i|,|A_j|)}=gcd(|A_i|,|A_j|))种循环。
所以在一个点的置换中，对(ans)的贡献为
(prodlimits_{i=1}^k{2^{frac{|A_i|}{2}}prodlimits_{j=i+1}^{k}{2^{gcd(|A_i|,|A_j|)}}})
考虑划分置换。
我们只需要知道置换中循环的大小，可通过拆分自然数的方式先将置换大小得出来。
在一个循环(A_i)中，为了其中元素只构成一个循环，有((|A_i|-1)!)中排列方式。
但是，对于长度相同的循环，交换一下我们就会认为组成新的循环，设(buk_i)为长度为(i)的循环的个数，则我们还有除以(prodlimits_{i=1}^{n}{buk_i!})。
( herefore ans=frac{1}{|S|}sumlimits_{自然数划分}{n!frac{prodlimits_{i=1}^k{2^{frac{|A_i|}{2}}prodlimits_{j=i+1}^{k}{2^{gcd(|A_i|,|A_j|)}}}}{prodlimits_{i=1}^k{|A_i|}prodlimits_{i=1}^n{buk_i!}}})
(n!)与(frac{1}{|S|})抵消，
(ans=sumlimits_{自然数划分}{frac{prodlimits_{i=1}^k{2^{frac{|A_i|}{2}}prodlimits_{j=i+1}^{k}{2^{gcd(|A_i|,|A_j|)}}}}{prodlimits_{i=1}^k{|A_i|}prodlimits_{i=1}^n{buk_i!}}})
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
using namespace std;
const int N=65,p=997;
int n,ans,buk[N],a[N],fac[N],gcd[N][N],er[N];
int Gcd(int x,int y){return y?Gcd(y,x%y):x;}
void pre(){
fac[0]=er[0]=1;
for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%p;
for(int i=1;i<=n;++i)
for(int j=i;j<=n;++j)
gcd[i][j]=gcd[j][i]=Gcd(i,j);
for(int i=1;i<=n;++i) er[i]=er[i-1]*2%p;
}
IL int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=c*a%p;
a=a*a%p,b>>=1;
}
return c;
}
void calc(int m){
int res=1,inv=1;memset(buk,0,sizeof(buk));
for(int i=1;i<=m;++i) res=res*er[a[i]>>1]%p;
for(int i=1;i<=m;++i)
for(int j=i+1;j<=m;++j)
res=res*er[gcd[a[i]][a[j]]]%p;
for(int i=1;i<=m;++i) ++buk[a[i]],inv=inv*a[i]%p;
for(int i=1;i<=n;++i) inv=inv*fac[buk[i]]%p;
ans=(ans+res*ksm(inv,p-2)%p)%p;
}
void dfs(int k,int i,int sum){
if(sum==n) return calc(k-1);
for(;i<=n-sum;++i) a[k]=i,dfs(k+1,i,sum+i);
}
int main()
{
scanf("%d",&n),pre();
if(n==0){puts("1");return 0;}
dfs(1,1,0),cout<<ans<<endl;
return 0;
}