bzoj1488[HNOI2009] 图的同构

2024-05-11 23:58

文章标签 hnoi2009 同构 bzoj1488

本文主要是介绍bzoj1488[HNOI2009] 图的同构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj1488
题目大意：
求两两互不同构的含n个点的简单图有多少种。
简单图是关联一对顶点的无向边不多于一条的不含自环的图。
a图与b图被认为是同构的是指a图的顶点经过一定的重新标号以后，a图的顶点集和边集能完全与b图一一对应。

题解：
置换-ploya
把一条边选和不选看成把一条边染成两种颜色之后，就跟bzoj1478/1815一样了..这样看来就是三倍经验了。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 80const int mod=997;
int ans,n,l[N],fac[N],gd[N][N],qm[10100];
int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);}
int qpow(int x,int t)
{int ret=1;while (t){if (t&1) ret=(ret*x)%mod;x=(x*x)%mod;t>>=1;}return ret;
}
void get_ans(int cnt)
{int i,j,c=0;for (i=1;i<=cnt;i++) c=c+l[i]/2;for (i=1;i<cnt;i++)for (j=i+1;j<=cnt;j++) c=c+gd[l[i]][l[j]];int now=1,tt=0;for (i=1;i<=cnt;i++){if (l[i]!=l[i-1]){now=(now*fac[tt])%mod;tt=0;}tt++;}now=(now*fac[tt])%mod;for (i=1;i<=cnt;i++) now=(now*l[i])%mod;int S=(fac[n]*qpow(now,mod-2))%mod;ans=(ans+(S*qm[c])%mod)%mod;
}
void div(int cnt,int x,int ret)
{if (ret==0) {get_ans(cnt);return;}if (x>ret) return;cnt++;while (x<=ret){l[cnt]=x;div(cnt,x,ret-x);x++;}
}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int i,j;scanf("%d",&n);qm[0]=1;for (i=1;i<=n*n;i++) qm[i]=(qm[i-1]*2)%mod;fac[0]=1;for (i=1;i<=n;i++) fac[i]=(fac[i-1]*i)%mod;for (i=1;i<=n;i++)for (j=i;j<=n;j++) gd[j][i]=gd[i][j]=gcd(i,j);ans=0;div(0,1,n);printf("%d\n",(ans*qpow(fac[n],mod-2))%mod);return 0;
}