参考 https://wenku.baidu.com/view/fee9e9b9bceb19e8b8f6ba7a.html?from=search### 的最后一道例题
首先无向完全图是个若干点的置换，但是实际上要染色边，也就是要求边的置换
首先，通过dfs构造一个点的置换，然后再把每个置换分割加起来就是答案（实际上分割方案很少）
那么现在有一个点置换的长度(a1,a2,a3...)，考虑边置换，一条边(pi,pj)，如果pi,pj在不同的置换里，那么显然循环节是lcm(ai,aj)，所以循环个数就是gcd(ao,aj)；
对于pi,pj在同一个置换里，如果a是奇数，那么只有循环节长度为2的循环个数就是(a-1)/2，如果是偶数，除了长度为2的循环节还有长度为a/2的，所以个数是a/2
然后一个拆分的方案数是https://blog.csdn.net/litble/article/details/79116659
#include<iostream>
#include<cstdio>
using namespace std;
const int N=60;
int n,m;
long long fac[N],mod,ans,a[N];
long long gcd(long long a,long long b)
{
return !b?a:gcd(b,a%b);
}
long long ksm(long long a,long long b)
{
long long r=1;
while(b)
{
if(b&1)
r=r*a%mod;
a=a*a%mod;
b>>=1;
}
return r;
}
void dfs(int w,int s,int y)
{
if(!y)
{
int c=0,tot=1;
long long nw=1;
for(int i=1;i<w;i++)
c+=a[i]/2;
for(int i=1;i<w;i++)
for(int j=i+1;j<w;j++)
c+=gcd(a[i],a[j]);
for(int i=1;i<w;i++)
nw=nw*a[i]%mod;
for(int i=2;i<w;i++)
{
if(a[i]!=a[i-1])
nw=nw*fac[tot]%mod,tot=0;
tot++;
}
nw=fac[n]*ksm(nw*fac[tot]%mod,mod-2)%mod;
ans=(ans+nw*ksm(m,c))%mod;
}
if(y<s)
return;
for(int i=s;i<=y;i++)
{
a[w]=i;
dfs(w+1,i,y-i);
}
}
int main()
{
scanf("%d%d%lld",&n,&m,&mod);
fac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
dfs(1,1,n);
printf("%lld
",ans*ksm(fac[n],mod-2)%mod);
return 0;
}