首页 > 代码库 > bzoj1488[HNOI2009]图的同构
bzoj1488[HNOI2009]图的同构
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1488
1488: [HNOI2009]图的同构
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 591 Solved: 388
[Submit][Status][Discuss]
Description
求两两互不同构的含n个点的简单图有多少种。
简单图是关联一对顶点的无向边不多于一条的不含自环的图。
a图与b图被认为是同构的是指a图的顶点经过一定的重新标号以后，a图的顶点集和边集能完全与b图一一对应。
Input
输入一行一个整数N，表示图的顶点数，0<=N<=60
Output
输出一行一个整数表示含N个点的图在同构意义下互不同构的图的数目，答案对997取模。
Sample Input
输入1
1
输入2
2
输入3
3
1
输入2
2
输入3
3
Sample Output
输出1
1
输出2
2
输出3
4
1
输出2
2
输出3
4
HINT
题目在这里 http://hi.baidu.com/fqq11679/blog/item/c277b9f8ff205e50252df2e9.html
Source
百度hi是什么。。
我怎么从来都不知道。。
这真是一道无聊而又无聊的题。。
看到同构两个字就想到了置换群和polya定理。。
但是。。
但是。。
但是。。
这道题要算的是边上的置换。。
感觉不可做。。
然后看了一发题解：http://blog.csdn.net/wzq_qwq/article/details/48035455
就会了
题解说的很详细了，就是把几个循环上的点拎出来再分类讨论一下，最后用polya定理算一下总答案就行了。
记得用逆元算啊。。
代码。。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define N 1010 6 #define mod 997 7 using namespace std; 8 int i,j,k,n,m,x,y,t,cnt,ans,fac[N],num[N],val[N]; 9 int gcd(int x,int y){return y==0?x:gcd(y,x%y);}10 int quickmi(int x,int y){11 if (y==1)return x;12 t=quickmi(x,y>>1);t=(t*t)%mod;13 return (y&1)?t*x%mod:t;14 }15 void dfs(int now,int x){16 if(x==0){17 int anow=0,la=1;18 for(int i=1;i<=cnt;i++){19 anow+=num[i]*(num[i]-1)/2*val[i]+val[i]/2*num[i];20 for(int j=i+1;j<=cnt;j++)anow+=num[i]*num[j]*gcd(val[i],val[j]);21 }22 for(int i=1;i<=cnt;i++){la=(la*quickmi(val[i],num[i])%mod*fac[num[i]])%mod; }23 la=quickmi(la,mod-2)*fac[n]%mod;24 ans=(ans+quickmi(2,anow)*la%mod)%mod; 25 }26 if(now>x)return;27 dfs(now+1,x);28 for(int i=1;i*now<=x;i++){val[++cnt]=now,num[cnt]=i;dfs(now+1,x-i*now);cnt--;}29 }30 int main(){31 scanf("%d",&n);32 fac[0]=1;for(i=1;i<=mod;i++)fac[i]=fac[i-1]*i%mod;33 dfs(1,n);34 ans=ans*quickmi(fac[n],mod-2)%mod;35 printf("%d\n",ans);36 return 0;37 }
都快noip了还在做这种跟noip无关的题。。
bzoj1488[HNOI2009]图的同构
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。