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...)...$

1. 对于不在一个循环里面的点： 比如$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$为置换之后仍为本身的数目，就是说要循环节里的每条边都一样的颜色）
2. 对于在一个循环里面的点： 比如$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);
}