[HNOI2009]图的同构

时间：2023-12-15 11:35:26

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

群论入门中
 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long lol;

 int Mod=;

 lol n,A[],ans,fac[],cnt,num[],p[];

 int gcd(int a,int b)

 {

   if (b==)

     return a;

   return gcd(b,a%b);

 }

 lol qpow(lol x,lol y)

 {

   lol res=;

   while (y)

     {

       if (y&) res=(res*x)%Mod;

       x=(x*x)%Mod;

       y/=;

     }

   return res;

 }

 void dfs(int now,int left)

 {int i,j;

   lol sum1=,sum2=;

   if (left==)

     {

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

     {

       sum1+=((num[i]-)*num[i]/)*p[i]+p[i]/*num[i];

       for (j=i+;j<=cnt;j++)

         sum1+=num[i]*num[j]*gcd(p[i],p[j]);

       sum2=sum2*fac[num[i]]*qpow(p[i],num[i])%Mod;

     }

       sum2=fac[n]*A[sum2%Mod];

       ans=(ans+sum2*qpow(,sum1)%Mod)%Mod;

       return;

     }

   if (now>left) return;

     dfs(now+,left);

   for (i=;i*now<=left;i++)

     {

       cnt++;

       p[cnt]=now;

       num[cnt]=i;

       dfs(now+,left-i*now);

       cnt--;

     }

 }

 int main()

 {int i;

   cin>>n;

   A[]=;A[]=;

   for (i=;i<=;i++)

     A[i]=((Mod-Mod/i)*A[Mod%i])%Mod;

   fac[]=;

   for (i=;i<=;i++)

     fac[i]=(fac[i-]*i)%Mod;

   dfs(,n);

   for (i=;i<=n;i++)

   ans=ans*A[i]%Mod;

   cout<<ans;

 }

相关文章