bzoj1488[HNOI2009]图的同构

2022-08-02 15:18:44

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1488

1488: [HNOI2009]图的同构

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 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

Sample Output

输出1
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定理算一下总答案就行了。

记得用逆元算啊。。

代码。。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define N 1010

 #define mod 997

 using namespace std;

 int i,j,k,n,m,x,y,t,cnt,ans,fac[N],num[N],val[N];

 int gcd(int x,int y){return y==?x:gcd(y,x%y);}

 int quickmi(int x,int y){

     if (y==)return x;

     t=quickmi(x,y>>);t=(t*t)%mod;

     return (y&)?t*x%mod:t;

 }

 void dfs(int now,int x){

     if(x==){

         int anow=,la=;

         for(int i=;i<=cnt;i++){

             anow+=num[i]*(num[i]-)/*val[i]+val[i]/*num[i];

             for(int j=i+;j<=cnt;j++)anow+=num[i]*num[j]*gcd(val[i],val[j]);

         }

         for(int i=;i<=cnt;i++){la=(la*quickmi(val[i],num[i])%mod*fac[num[i]])%mod; }

         la=quickmi(la,mod-)*fac[n]%mod;

         ans=(ans+quickmi(,anow)*la%mod)%mod;

     }

     if(now>x)return;

     dfs(now+,x);

     for(int i=;i*now<=x;i++){val[++cnt]=now,num[cnt]=i;dfs(now+,x-i*now);cnt--;}

 }

 int main(){

     scanf("%d",&n);

     fac[]=;for(i=;i<=mod;i++)fac[i]=fac[i-]*i%mod;

     dfs(,n);

     ans=ans*quickmi(fac[n],mod-)%mod;

     printf("%d\n",ans);

     return ;

 }

都快noip了还在做这种跟noip无关的题。。

码农公寓