burnside+polya
首先将图中的所有无向边，存在就染成1，不存在就染成2，问题就转化成了一个完全图的染色问题 完全图的染色问题在08年的论文：陈瑜希《Pólya计数法的应用》中有详细题解，算比较清楚了 然后就不想写了，翻论文吧，绝对比我写的要清晰
code：
#include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<cmath> #include<ctime> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<climits> #include<complex> #include<iostream> #include<algorithm> #define ll long long using namespace std; const int maxn = 80; const int Mod = 997; int ny[Mod+10],pw[maxn*maxn]; int gcd(int a,int b){return a==0?b:gcd(b%a,a);} void prepare() { ny[1]=1; for(int i=2;i<Mod;i++) ny[i]=(((-Mod/i)*ny[Mod%i]%Mod)+Mod)%Mod; } int ret,n,temp; int a[maxn]; void solve(int nw,int down,int up,int s) { if(!up) { int k=0,t=1,r=temp; for(int i=1;i<nw;i++) { if(a[i]!=a[i-1]) { r=r*ny[t]%Mod; t=1; k=0; } r=r*ny[a[i]]%Mod; k++; t=t*k%Mod; } r=r*ny[t]%Mod; ret=(ret+pw[s]*r)%Mod; return ; } for(int i=down;i<=up;i++) { if(i!=up&&up-i<i) continue; a[nw]=i; int l=i/2; for(int j=1;j<nw;j++) l=(l+gcd(i,a[j]))%Mod; solve(nw+1,i,up-i,s+l); } } int main() { prepare(); pw[0]=1; for(int i=1;i<maxn*maxn;i++) pw[i]=(pw[i-1]<<1)%Mod; scanf("%d",&n); temp=1; for(int i=1;i<=n;i++) temp=temp*i%Mod; ret=0; solve(1,1,n,0); ret=ret*ny[temp]%Mod; printf("%d\n",ret); return 0; }