本文共 2331 字，大约阅读时间需要 7 分钟。

题目链接

思路

显然有$N!$个边的置换，枚举边的置换肯定不可行。
因此，我们来考虑点置换和边置换的关系。
首先，考虑一条边$(x,y)$。

如果$x$和$y$在点置换中的同一循环节中，设这个循环节长度为$L$。
若$L$为奇数，则$(x,y)$所处边置换中循环节长度为$L$，一共有$C_L^2$条边，所以循环节的个数为$\frac{C_L^2}{L}=\frac{L-1}{2}$个。
若$L$为偶数，则$(x,y)$所处边置换，出来上述长度为$L$的情况，还有一种情况：
如果$x,y$在循环节中正好相距$\frac{L}{2}$，那么循环节长度为$\frac{L}{2}$这样的循环节一共有$\frac{L}{2}$个，循环节的个数为$\frac{C_L^2-\frac{L}{2}}{L}+1=\frac{L}{2}$个循环节。

再来考虑$x,y$不在一个循环节的情况，设循环节长度分别为$L_1,L_2$。
显然，$(x,y)$所在置换的循环节长度为$lcm(L_1,L_2)$，这样的循环节个数为$\frac{L_1L_2}{lcm(L_1,L_2)}=gcd(L_1,L_2)$个。

若一个点置换的循环节长度分别为$L_1,L_2,\cdots ,L_K$，那么边置换的循环节长度为：

接下来我们求满足循环节长度为$L_1,L_2,\cdots,L_K$的边置换个数。
这就相当于将$1\cdots N$放入大小为$L_1,L_2,\cdots,L_K$的环中，求总方案数。
显然，如$L$不重复，那么总方案数为$\frac{N!}{L_1L_2\cdots L_K}$，这里不给出证明了。
若$L$有重复，假设$L$中有$t$种不同的值，第$i$种值的个数为$k_i$，那么总方案数（也就是满足条件的边置换个数）为：

最终的答案为：

代码

#include <cstdio>const int maxn=53;int fac[maxn+1],l[maxn+1],n,m,p,ans;int gcd(int x,int y){  return y?gcd(y,x%y):x;}inline int quickpow(int a,int b,int mo){  int res=1;  while(b)    {      if(b&1)        {          res=1ll*res*a%mo;        }      a=1ll*a*a%mo;      b>>=1;    }  return res;}inline int getans(int x){  int c=0,s=1,cnt=0;  for(register int i=1; i<=x; ++i)    {      c+=l[i]/2;      for(register int j=i+1; j<=x; ++j)        {          c+=gcd(l[i],l[j]);        }      s=(1ll*s*l[i])%p;      if(l[i]!=l[i-1])        {          s=(1ll*s*fac[cnt])%p;          cnt=0;        }      ++cnt;    }  s=(1ll*s*fac[cnt])%p;  s=(1ll*fac[n]*quickpow(s,p-2,p))%p;  ans=(1ll*ans+((1ll*s*quickpow(m,c,p))%p))%p;  return 0;}int search(int now,int lo,int hi){  if(!hi)    {      getans(now-1);    }  if(hi<lo)    {      return 0;    }  for(register int i=lo; i<=hi; ++i)    {      l[now]=i;      search(now+1,i,hi-i);      l[now]=0;    }  return 0;}int main(){  scanf("%d%d%d",&n,&m,&p);  fac[0]=1;  for(register int i=1; i<=n; ++i)    {      fac[i]=(1ll*fac[i-1]*i)%p;    }  search(1,1,n);  printf("%d\n",(int)((1ll*ans*quickpow(fac[n],p-2,p))%p));  return 0;}