<div class="post_brief"><p>
一道burnside，做了几次之后感觉比较经典了。然后发现网上居然没有题解。</p>

 

枚举正整数拆分，既每个质换的长度。然后枚举gcd算每类置换的贡献。再用错排公式来算每类置换的数量。然后求和。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


#define _l (long long int)


const int maxn = 63;


int n, m, mod, ans, g[maxn][maxn];
int sq[maxn], tq, fac[maxn], finv[maxn], vinv[maxn];


int modPow(int a, int x) {
int s(1);
for (; x; x >>= 1, a = _l a * a % mod)
if (x & 1)
s = _l s * a % mod;
return s;
}


int gcd(int a, int b) {
while (a) {
register int c(b % a);
b = a;
a = c;
}
return b;
}


void addAns() {
int t(0);
for (int i = 1; i <= tq; ++ i) {
t += sq[i] >> 1;
//	if (sq[i] > 1)
//		++ t;
for (int j = 1; j < i; ++ j)
t += g[sq[i]][sq[j]];
}
t = modPow(m, t);
for (int i = 1, j; i <= tq; i = j) {
for (j = i; j <= tq && sq[i] == sq[j]; ++ j)
t = _l t * vinv[sq[j]] % mod;
t = _l t * finv[j - i] % mod;
}
ans = (ans + t) % mod;
}


void dfs(int v, int l) {
if (!v)
addAns();
else {
++ tq;
for (int i = 1; i <= l && i <= v; ++ i) {
sq[tq] = i;
dfs(v - i, i);
}
– tq;
}
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


scanf("%d%d%d", &amp;n, &amp;m, &amp;mod);
fac[0] = finv[0] = 1;
for (int i = 1; i &lt;= n; ++ i) {
	fac[i] = _l fac[i - 1] * i % mod;
	finv[i] = modPow(fac[i], mod - 2);
	vinv[i] = modPow(i, mod - 2);
	for (int j = 1; j &lt;= n; ++ j)
		g[i][j] = gcd(i, j);
}
tq = 0;
dfs(n, n);
printf("%d\n", ans);



}