【HNOI2009】bzoj1488 图的同构

本文主要是介绍【HNOI2009】bzoj1488 图的同构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先可以把问题转化成在完全图上对边进行黑白染色。
对于每个点的置换，要求出有多少关于边的不动点。把置换分解成循环，可以发现，一个长度为$x$的点的循环内部有$\lfloor\frac x2\rfloor$个边的循环，两个长度为$x$和$y$的点的循环之间有$\gcd(x,y)$个边的循环，这样关于边的不动点总数就是$2^m$，其中$m$表示边的循环的总数。
但是直接枚举点的置换有$n!$种，显然无法承受。因为每种置换对答案的贡献只和每个循环的大小有关，可以枚举$n$的正整数拆分，然后对每种拆分计算对应的置换个数。具体来说，记有$m$个循环，每个循环的长度为$l_i$,每个长度的循环有$c_i$个。首先给每个循环分配一个位置

$$\binom{n}{l_1}\binom{n-l_1}{l_2}\cdots\binom{n-l_1-\cdots-l_{m-1}}{l_m}=\frac{n!}{\prod l_i!}$$
然后，固定第一个元素，每个循环有 $(l_i-1)!$种排法。同时，相同长度的循环彼此之间的顺序被重复考虑。所以最后的答案是
$$\frac{n!}{\prod l_i\prod c_i}$$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int p=997;
int n,ans,fac[65],inv[65],invfac[65],cnt[65],a[65],gcd[65][65],node;
int pow(int base,int k)
{int ret=1;for (;k;k>>=1,base=base*base%p)if (k&1) ret=ret*base%p;return ret;
}
int getgcd(int x,int y)
{if (gcd[x][y]) return gcd[x][y];return gcd[x][y]=y?getgcd(y,x%y):x;
}
void check()
{int ret=fac[n],tot=0,sum=0;for (int i=1;i<=n;i++){ret=ret*invfac[cnt[i]]%p;for (int j=1;j<=cnt[i];j++)a[++tot]=i,ret=ret*inv[i]%p;}for (int i=1;i<=tot;i++){sum+=a[i]/2;for (int j=i+1;j<=tot;j++) sum+=gcd[a[i]][a[j]];}ret=ret*pow(2,sum)%p;ans=(ans+ret)%p;
}
void dfs(int now,int num)
{//node++;if (now==1){cnt[1]=n-num;check();return;}for (int i=0;num+i*now<=n;i++){cnt[now]=i;dfs(now-1,num+i*now);}
}
int main()
{scanf("%d",&n);fac[0]=invfac[0]=1;for (int i=1;i<=n;i++){fac[i]=fac[i-1]*i%p;inv[i]=pow(i,p-2);invfac[i]=pow(fac[i],p-2);}for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)gcd[i][j]=getgcd(i,j);dfs(n,0);//printf("%d\n",node);printf("%d\n",ans*invfac[n]%p);
}

这篇关于【HNOI2009】bzoj1488 图的同构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---