求两两互不同构的含n个点的简单图有多少种。
简单图是关联一对顶点的无向边不多于一条的不含自环的图。
a图与b图被认为是同构的是指a图的顶点经过一定的重新标号以后，a图的顶点集和边集能完全与b图一一对应。输入一行一个整数N，表示图的顶点数，0<=N<=60
输出一行一个整数表示含N个点的图在同构意义下互不同构的图的数目，答案对997取模。
题目在这里 http://hi.baidu.com/fqq11679/blog/item/c277b9f8ff205e50252df2e9.html
题解：置换＋dfs
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 103 #define p 997 #define LL long long using namespace std; int n,num[N],k[N]; LL cnt,c[N][N],ans,d[N],jc[N],inv[N],a[N],g[N][N],b[N*N]; LL quickpow(LL num,int x) { LL ans=1; LL base=num%p; while (x) { if (x&1) ans=ans*base%p; x>>=1; base=base*base%p; } return ans; } void init(int n) { for (int i=0;i<=n;i++) c[i][0]=1; for (int i=1;i<=n;i++) for (int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%p; jc[0]=1; for (int i=1;i<=n;i++) jc[i]=jc[i-1]*i%p; for (int i=1;i<=n;i++) inv[i]=quickpow(jc[i],p-2); b[0]=1; for (int i=1;i<=n*n;i++) b[i]=b[i-1]*2%p; } int gcd(int x,int y){ if (g[x][y]) return g[x][y]; int r; while (y){ r=x%y; x=y; y=r; } return g[x][y]=x; } void dfs(int x,int now) { if (!now) { int n1=x-1; int sum=0; for (int i=1;i<=n1;i++) for (int j=i+1;j<=n1;j++) sum+=gcd(a[i],a[j]); for (int i=1;i<=n1;i++) sum+=a[i]/2; LL tot=1; int cnt=n; for (int i=1;i<=n1;i++) tot=tot*c[cnt][a[i]]%p,cnt-=a[i]; for (int i=1;i<=n;i++) if (k[i]) tot=tot*inv[k[i]]%p; for (int i=1;i<=n1;i++) tot=tot*jc[a[i]-1]%p; ans=(ans+tot*b[sum])%p; //cout<<tot<<" "<<sum<<endl; return; } for (int i=a[x-1];i<=now;i++) { k[i]++; a[x]=i; dfs(x+1,now-i); k[i]--; } } int main() { scanf("%d",&n); if (n==1) { printf("1\n"); return 0; } a[0]=1; init(n); dfs(1,n); ans=ans*quickpow(jc[n],p-2)%p; printf("%lld\n",ans); }