「HNOI2009」图的同构 - 数论+Polya计数 | Bill Yang's Blog

「HNOI2009」图的同构 - 数论+Polya计数

题目大意

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


题目分析

把有边与无边看做二染色,就和上题一模一样了。
水水水水水水~


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=65,p=997;
int n,a[maxn],G[maxn][maxn];
LL Pow[maxn*maxn+maxn],fac[maxn],inv[maxn],invf[maxn],ans=0;
int gcd(int a,int b) {return b==0?a:(G[a][b]?G[a][b]:G[a][b]=gcd(b,a%b));}
void Dfs(int dep,int sum,int last) {
if(!sum) {
LL s=fac[n],c=0,len=0;
for(int i=1; i<=dep; i++) {
len++;
if(i==dep||a[i]!=a[i+1])s=s*invf[len]%p,len=0;
s=s*inv[a[i]]%p;
c+=a[i]>>1;
for(int j=1; j<i; j++)c+=gcd(a[i],a[j]);
}
ans=(ans+Pow[c]*s)%p;
return;
}
for(int i=min(sum,last); i>=1; i--)a[dep+1]=i,Dfs(dep+1,sum-i,i);
}
int main() {
n=Get_Int();
Pow[0]=1;
for(int i=1; i<=n*n+n; i++)Pow[i]=Pow[i-1]*2%p;
fac[1]=inv[1]=invf[1]=fac[0]=inv[0]=invf[0]=1;
for(int i=2; i<=n; i++) {
fac[i]=fac[i-1]*i%p;
inv[i]=p-(p/i)*inv[p%i]%p;
invf[i]=invf[i-1]*inv[i]%p;
}
Dfs(0,n,n);
printf("%lld\n",ans*invf[n]%p);
return 0;
}
大佬赏瓶冰阔落吧~
0%