#题目描述
\(n\le 60\)个点的无向图有几种?
#做法
搜索,见08年陈瑜希论文
#AC Code
打表
#include <iostream>
using namespace std;
int ans[]=
{
1,
1,
2,
4,
11,
34,
156,
47,
382,
493,
291,
56,
400,
993,
778,
96,
890,
888,
766,
749,
7,
304,
785,
887,
46,
799,
403,
68,
742,
852,
567,
582,
803,
231,
122,
61,
761,
151,
931,
617,
870,
170,
736,
521,
412,
976,
217,
383,
119,
447,
314,
793,
952,
321,
665,
663,
780,
791,
78,
403,
683
};
int main()
{
int n;
cin>>n;
cout<<ans[n]<<endl;
return 0;
}
Q:为毛下面这个WA了,到n=46都是对的……
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,ans;
const int mod=997;
int h[65],a[65],f[5005];
int g[65][65];
int gcd(int x,int y)
{
if (y==0)
return x;
else
return gcd(y,x%y);
}
int Pow(int n,int k)
{
int r=1;
for (;k;k>>=1,(n*=n)%=mod)
if (k&1)
(r*=n)%=mod;
return r;
}
void dfs(int dep,int n,int last,int t,int l,int k)
{
int tt,kk;
if (n==0)
(ans+=t*f[k])%=mod;
else
{
tt=t;kk=k;
for (int i=last;i<=n;i++)
{
a[dep]=i;t=tt;k=kk;
t=t*f[i>>1]*h[i]%mod;
for (int j=1;j<=dep-1;j++)(k+=g[a[j]][i])%=mod;
if (i==a[dep-1])l++;else l=1;
(t*=h[l])%=mod;
dfs(dep+1,n-i,i,t,l,k);
}
}
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
g[i][j]=gcd(i,j);
f[0]=1;
for (int i=1;i<=5000;i++)
f[i]=(f[i-1]*2)%mod;
for (int i=1;i<=n;i++)
h[i]=Pow(i,mod-2);
dfs(1,n,1,1,0,0);
cout<<ans<<endl;
return 0;
}