有色图

题目链接：ybt金牌导航8-5-4 / luogu P4128

题目大意

有个 n 个点的无向完全图，然后每个边会有颜色，一共有 m 种颜色。
然后如果一个完全图一个图可以通过置换变成另一个图，那我们就说这两个完全图是本质相同的。
然后问你有多少本质不同的图。

思路

我们考虑用 Polya 定理。

\(ans=\dfrac{1}{|M|}\sum m^{c(r)}\)

然后你考虑如何求每个 \(c(r)\) 即循环个数。
然后你发现你前面的 \(|M|\) 是点的置换（是 \(n!\)），然后你 \(c(r)\) 里面要的是边的置换循环个数。

那你就考虑怎么求，考虑边的置换方式：
然后你考虑先把点的置换表示出来：\((a_1,a_2,...)(b_1,b_2,...)(c_1,c_2,...)...\)，它们每个循环的长度可以表示为 \(l_1,l_2,l_3,...\)。

然后你考虑边的置换方式其实可以分类成两种：

1. 边连接的两个点在不同点循环：

假设两个点所在的循环是 \((a_1,a_2,...),(b_1,b_2,...)\)，然后长度分别是 \(l_1,l_2\)。
然后不难看出边的循环节都是 \(\text{lcm}(l_1,l_2)\)，然后一共边有 \(l_1l_2\) 个点对，所以就是 \(\dfrac{l_2l_2}{\text{lcm}(l_1,l_2)}=\gcd(l_1,l_2)\)。

1. 边链接的两个点在同一个点循环。

假设这个循环是 \((a_1,a_2,...)\)，长度是 \(l\)。

那我们再分奇偶讨论。

如果长度是奇数，就是循环节是 \(l\)，一共 \(\binom{l}{2}\) 个点对，就是 \(\dfrac{l-1}{2}\) 个循环个数。
如果长度是偶数，那还会有一种特殊的置换，就是两个点间隔 \(\dfrac{l}{2}\)，这样它走一样就位置交换，那由于你是无向的边，所以就循环节是 \(\dfrac{l}{2}\)。那就是 \(\dfrac{\binom{l}{2}-\frac{l}{2}}{l}+1=\dfrac{l}{2}\)。

其实我们总结一下，就是 \(\left\lfloor\dfrac{l}{2}\right\rfloor\)。

那我们就可以知道对于一个点置换，它边置换的循环数就是 \(\sum\limits_{i=1}^l\left\lfloor\dfrac{l_i}{2}\right\rfloor+\sum\limits_{i=1}^l\sum\limits_{j=i+1}^l\gcd(l_i,l_j)\)

然后我们考虑怎么统计每个置换的答案，直接枚举肯定是不行的。
那我们考虑把 \(l_i\) 排序，然后对于排序后的结果我们直接暴力枚举，然后用组合数算出有多少种置换在排序后会变成这样。

首先暴力枚举由于每次新的数一定会小于等于之前的数，而且所有数的和已经确定，所以这个复杂度看似很大其实不大。（见 A296010）
然后你考虑怎么用组合数算有多少中置换。

一开始直接看 \(1\sim n\) 每个点在哪个循环，那就是一个多重组合数：\(\dfrac{n!}{\prod l_i!}\)。
那每个置换，你可以分配它内部的顺序，如果是链就是 \(l_i!\)，但是由于你是环，可以转，所以是 \((l_i-1)!\)，然后每个都这么乘，那它就变成了 \(\dfrac{n!}{\prod l_i}\)。
然后你发现还是会算重，因为你相同长度的置换你交换了不一样，所以还要每个除 \(\dfrac{1}{\prod c_i!}\)。（\(c_x=\sum [l_i=x]\)）

然后全部合起来：
\[\dfrac{1}{n!}\sum\limits_{l}\dfrac{n!}{\prod l_i\prod c_i!}m^{\sum\limits_{i}\left\lfloor\frac{l_i}{2}\right\rfloor+\sum\limits_{i=1}^l\sum\limits_{j=i+1}^l\gcd(l_i,l_j)}\]

然后里外的 \(n!\) 互相消去：
\[\sum\limits_{l}\dfrac{1}{\prod l_i\prod c_i!}m^{\sum\limits_{i}\left\lfloor\frac{l_i}{2}\right\rfloor+\sum\limits_{i=1}^l\sum\limits_{j=i+1}^l\gcd(l_i,l_j)}\]

然后就可以搞了。

代码

#include
#define ll long long

using namespace std;

ll n, m, mo, b[55], jc[55], ans, inv[55];

ll ksm(ll x, ll y) {
    ll re = 1;
    while (y) {
        if (y & 1) re = re * x % mo;
        x = x * x % mo;
        y >>= 1;
    }
    return re;
}

ll gcd(ll x, ll y) {
    if (!y) return x;
    return gcd(y, x % y);
}

//ll clac(ll cnt) {//这些就直接每加一个就直接统计了，就不用这个了
//  ll re = 0;
//  
//  for (int i = 1; i <= cnt; i++) {
//      re += b[i] / 2;
//      for (int j = i + 1; j <= cnt; j++)
//          re += gcd(b[i], b[j]);
//  }
//  
//  return ksm(m, re);
//}

void dfs(ll now, ll num, ll di, ll cnt, ll sum) {
    if (now == n) {
        ans = (ans + ksm(m, sum) * di % mo) % mo;
        return ;
    }
    if (num == 1) {
        for (int i = 1; i <= n - now; i++) {
            b[cnt + i] = 1;
            sum = sum + b[cnt + i] / 2;
            for (int j = 1; j < cnt + i; j++)
                sum = sum + gcd(b[cnt + i], b[j]);
            di = di * inv[i] % mo;
        }
        ans = (ans + ksm(m, sum) * di % mo) % mo;
        return ;
    }
    dfs(now, num - 1, di, cnt, sum);
    for (int i = 1; now + num * i <= n; i++) {//枚举这个数放的个数
        b[cnt + i] = num;
        sum = sum + b[cnt + i] / 2;
        for (int j = 1; j < cnt + i; j++)
            sum = sum + gcd(b[cnt + i], b[j]);
        di = di * inv[num] % mo * inv[i] % mo;
        dfs(now + num * i, num - 1, di, cnt + i, sum);
    } 
}

int main() {
    scanf("%lld %lld %lld", &n, &m, &mo);
    
    jc[0] = 1; for (int i = 1; i <= n; i++) jc[i] = jc[i - 1] * i % mo;//预处理
    inv[0] = inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
    dfs(0, n, 1, 0, 0);
    
    printf("%lld", ans);
    
    return 0;
}