Description
给 定一个$N$个结点的无向完全图（ 任意两个结点之间有一条边）， 现在你可以用 $M$ 种颜色对这个图的每条边进行染色，每条边必须染一种颜色。 若两个已染色的图，其中一个图可以通过结点重新编号而与另一个图完全相同， 就称这两个染色方案相同。 现在问你有多少种本质不同的染色方法，输出结果 $mod P$。$P$ 是一个大于$N$的质数。
Input
仅一行包含三个数，$N$、$M$、$P$。
Output
仅一行，为染色方法数 $mod P$ 的结果。
Sample Input
3 4 97
Sample Output
20
题解
假定一个点置换，把它表示为循环，比如是$(a_1,a_2,….)(b_1,b_2…)(c_1,c_2…)…$
- 对于不在一个循环里面的点： 比如$a1,b1$, 那么会有边循环$((a1,b1),(a2,b2)…)$设$a$循环的循环节是$l1,b$循环的循环节是$l2$,那么形成的边循环的循环节显然是$LCM(l1,l2)$。一共有$l1*l2$个点对，每个点对都在一个循环节为$LCM(l1,l2)$的循环上，所以一共有$l1*l2/LCM(l1,l2)=GCD(l1,l2)$个循环节，所以$C(f)=m^GCD(l1,l2)$。（回到$Burnside$引理，$C$为置换之后仍为本身的数目，就是说要循环节里的每条边都一样的颜色）
- 对于在一个循环里面的点： 比如$a1$、$a2$。设这个$a$循环的循环节为$l1$。
- 如果$l1$是奇数，那么循环长度为$l1$，一共有$C(l1,2)$个点对，所以是$(l1-1)/2$个循环节，所以$C(f)=m^((l1-1)/2)$。
- 如果$l1$是偶数，除了上面这种情况之外，还有一种的循环节是$l1/2$（就是两个点刚好相隔半个周期，而边是双向的），所以一共有$(C(l1,2)-l1/2)/l1+1=l1/2$个点对。
整理一下：
$$C = \sum_{i = 1}^{k}{\lfloor \frac{L_i}{2} \rfloor} + \sum_{i = 1}^{k - 1}{\sum_{j = i + 1}^{k} {gcd(L_i, L_j)} }$$
$$S = \frac{ N! }{\prod_{i = 1} ^ {k} \times \prod_{i = 1}^{k}{ B_i! } }$$
$$Ans = Ans + S \times m^C$$
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int MOD;
const int MAXN = 1005;
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
int gd[MAXN][MAXN], f[MAXN];
long long pow_mod(long long a, int b)
{
long long ans = 1;
while (b)
{
if (b & 1) ans = ans * a % MOD;
b >>= 1;
a = a * a % MOD;
}
return ans;
}
int l[MAXN];
long long ans;
int n, m;
void Get_Ans(int cnt)
{
long long C = 0;
for (int i = 1; i <= cnt; i++) C = (C + l[i] / 2) % MOD;
for (int i = 1; i <= cnt; i++)
for (int j = i + 1; j <= cnt; j++)
C = (C + gd[l[i]][l[j]]) % MOD;
long long now = 1, len = 0;
for (int i = 1; i <= cnt; i++)
{
if (l[i] != l[i - 1])
{
now = now * f[len] % MOD;
len = 0;
}
len++;
}
now = now * f[len] % MOD;
for (int i = 1; i <= cnt; i++) now = now * l[i] % MOD;
long long S = f[n] * pow_mod(now, MOD - 2) % MOD;
ans = (ans + S * pow_mod(m, C) % MOD) % MOD;
}
void DFS(int cnt, int x, int les)
{
if (les == 0) return Get_Ans(cnt);
if (les < x) return;
cnt++;
while (x <= les)
{
l[cnt] = x;
DFS(cnt, x, les - x);
x++;
}
}
int main()
{
n = read(), m = read();
MOD = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
gd[i][j] = gcd(i, j);
0[f] = 1;
for (int i = 1; i <= n; i++)
i[f] = 1ll * ((i - 1)[f]) * i % MOD;
ans = 0;
DFS(0, 1, n);
printf ("%lld\n", ans * pow_mod(f[n], MOD - 2) % MOD);
}