P4727 [HNOI2009] 图的同构计数
[题目通道]([HNOI2009] 图的同构计数 - 洛谷)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 997
#define MAX 75
int n,ans,jc[MOD],inv[MOD],jv[MOD];
int g[MAX][MAX],a[MAX],b[MAX],bin[MAX*MAX];
void calc()
{int ret=jc[n],tot=0,sum=0;for(int i=1;i<=n;++i){ret=ret*jv[a[i]]%MOD;for(int j=1;j<=a[i];++j)ret=ret*inv[i]%MOD,b[++tot]=i;}for(int i=1;i<=tot;++i)sum+=b[i]/2;for(int i=1;i<=tot;++i)for(int j=i+1;j<=tot;++j)sum+=g[b[i]][b[j]];ret=ret*bin[sum]%MOD;ans=(ans+ret)%MOD;
}
void dfs(int x,int sum)
{if(x==1){a[x]=n-sum;calc();return;}for(int i=0;sum+i*x<=n;++i)a[x]=i,dfs(x-1,sum+i*x);
}
int main()
{scanf("%d",&n);jc[0]=jv[0]=inv[0]=inv[1]=bin[0]=1;for(int i=2;i<MOD;++i)inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;for(int i=1;i<MOD;++i)jc[i]=jc[i-1]*i%MOD;for(int i=1;i<MOD;++i)jv[i]=jv[i-1]*inv[i]%MOD;for(int i=1;i<MAX*MAX;++i)bin[i]=bin[i-1]*2%MOD;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)g[i][j]=__gcd(i,j);dfs(n,0);ans=ans*jv[n]%MOD;printf("%d\n",ans);return 0;
}