题解 P4727 【[HNOI2009]图的同构记数】
斯德哥尔摩
2018-07-29 18:21:24
这题感觉像是$Polya$计数。。。
然后借鉴了这位大佬的博客证明了这题是$Polya$计数：[博客](https://blog.csdn.net/sdfzyhx/article/details/70035662)
首先，我们可以把问题转化成在完全图上对边进行黑白染色，求不同构方案数。
然后就跟这题差不多了：[P4128 [SHOI2006]有色图](https://www.luogu.org/problemnew/show/P4128)
对于每个点的置换，要求出有多少关于边的不动点。
把置换写成循环，可以发现两条性质：
1. 一个长度为$x$的点的循环内部有$\lfloor \frac{x}{2}\rfloor$个边的循环。
2. 两个长度分别为$x$和$y$的点的循环之间有$gcd(x,y)$个边的循环，这样关于边的不动点总数就是$2m$，其中$m$表示边的循环的总数。
但是直接枚举点的置换有$n!$种，$TLE$。
我们考虑，因为每种置换对答案的贡献只和每个循环的大小有关，可以枚举$n$的正整数拆分，然后对每种拆分计算对应的置换个数。
具体来说，记有$m$个循环，每个循环的长度为$l_i$,每个长度的循环有$c_i$个。
首先给每个循环分配一个位置：
$$\left(\begin{array}{c}n\\l_1\end{array}\right)\left(\begin{array}{c}n-l_1\\l_2\end{array}\right)...\left(\begin{array}{c}n-l_1-l_2-...-l_{m-1}\\l_m\end{array}\right)$$
然后固定第一个元素，每个循环有 $(l_i-1)!$ 种排法。
但是相同长度的循环彼此之间的顺序被重复考虑。
所以最后的答案就可求了：
$$Ans=\frac{n!}{\prod_{i=1}^ml_i\prod_{i=1}^mc_i}$$
除转乘直接逆元，而$997\in prime$，所以直接费马小定理即可。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 70
#define MOD 997
using namespace std;
long long n,ans=0;
long long val[MAXN],num[MAXN],fact[MAXN],inv[MAXN],invfact[MAXN],gcd[MAXN][MAXN];
inline long long read(){
long long date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
long long Gcd(long long x,long long y){//记忆化gcd
if(gcd[x][y])return gcd[x][y];
else if(!y)return x;
return Gcd(y,x%y);
}
long long mexp(long long a,long long b,long long c){//快速幂应该都会
long long s=1;
while(b){
if(b&1)s=s*a%c;
a=a*a%c;
b>>=1;
}
return s;
}
void get_answer(){//累计答案
int top=0;
long long sum=0,now=fact[n];
for(int i=1;i<=n;i++){
now=now*invfact[num[i]]%MOD;
for(int j=1;j<=num[i];j++){
val[++top]=i;
now=now*inv[i]%MOD;
}
}
for(int i=1;i<=top;i++){
sum+=val[i]/2;
for(int j=i+1;j<=top;j++)sum+=gcd[val[i]][val[j]];
}
now=now*mexp(2,sum,MOD)%MOD;
ans=(ans+now)%MOD;
}
void dfs(int x,int s){//直接暴搜
if(x==1){
num[1]=n-s;
get_answer();
return;
}
for(int i=0;s+i*x<=n;i++){
num[x]=i;
dfs(x-1,s+i*x);
num[x]=0;
}
}
void work(){
dfs(n,0);
ans=ans*invfact[n]%MOD;//别忘了！
printf("%lld\n",ans);
}
void init(){//预处理阶乘、逆元、gcd
n=read();
fact[0]=invfact[0]=1;
for(int i=1;i<=n;i++){
fact[i]=fact[i-1]*i%MOD;
inv[i]=mexp(i,MOD-2,MOD);
invfact[i]=mexp(fact[i],MOD-2,MOD);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
gcd[i][j]=Gcd(i,j);
}
int main(){//主函数So easy!
init();
work();
return 0;
}
```