由于有很多本质相同的重复置换，我们先枚举各种长度的点循环分别有多少个，这个暴搜的复杂度不大，n=53时也只有3e5左右。对于每种搜索方案可以轻易求出它所代表的置换具体有多少个。
但我们搜索的是点置换组成的循环，要求的是边置换组成的循环。现在问题就是对于每种搜索方案，求出有多少个边循环。
首先，如果一条边的两个端点属于同一点循环，另一条边的端点属于两个不同点循环，那么显然这两条边不可能属于同一边循环。
对于一个长度为L的点循环，观察发现所有两个端点都属于这个点循环的边构成了L/2个边循环。
对于两个长度分别为L1,L2的点循环，由于每条端点分别在这两个点循环中的边都是等价的，所有所有循环长度相等。显然每个循环长度为lcm(L1,L2)，所以边共组成gcd(L1,L2)个边循环。
由Polya定理直接得解。
同理[BZOJ1488]可以看作一个完全图的黑白染色，直接令m=2即可。
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 typedef long long ll; 5 using namespace std; 6 7 const int N=60; 8 int n,m,mod,ans,tot,sm,fac[N],inv[N],Inv[N],L[N]; 9 10 int gcd(int a,int b){ return b ? gcd(b,a%b) : a; } 11 12 int ksm(int a,int b){ 13 int res=1; 14 for (; b; a=1ll*a*a%mod,b>>=1) 15 if (b & 1) res=1ll*res*a%mod; 16 return res; 17 } 18 19 void dfs(int x,int lst){ 20 if (x>n){ 21 int s=0,cnt=fac[n],same=1; 22 rep(i,1,tot){ 23 s+=L[i]/2; 24 rep(j,i+1,tot) s+=gcd(L[i],L[j]); 25 cnt=1ll*cnt*Inv[L[i]]%mod; 26 if (i>1 && L[i]==L[i-1]) same++; 27 else cnt=1ll*cnt*inv[same]%mod,same=1; 28 } 29 cnt=1ll*cnt*inv[same]%mod; 30 sm=(sm+cnt)%mod; ans=(ans+1ll*cnt*ksm(m,s))%mod; 31 return; 32 } 33 rep(i,lst,n-x+1) L[++tot]=i,dfs(x+i,i),tot--; 34 } 35 36 int main(){ 37 freopen("bzoj1815.in","r",stdin); 38 freopen("bzoj1815.out","w",stdout); 39 scanf("%d%d%d",&n,&m,&mod); 40 fac[0]=inv[0]=Inv[1]=1; 41 rep(i,2,n) Inv[i]=1ll*(mod-mod/i)*Inv[mod%i]%mod; 42 rep(i,1,n) fac[i]=1ll*fac[i-1]*i%mod; 43 inv[n]=ksm(fac[n],mod-2); 44 for (int i=n-1; i; i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; 45 dfs(1,1); printf("%lld ",1ll*ans*ksm(sm,mod-2)%mod); 46 return 0; 47 }