洛谷P4128 [SHOI2006] 有色图题解

题目链接：P4128 [SHOI2006] 有色图

题意：

如果一张无向完全图（完全图就是任意两个不同的顶点之间有且仅有一条边相连）的每条边都被染成了一种颜色，我们就称这种图为有色图。如果两张有色图有相同数量的顶点，而且经过某种顶点编号的重排，能够使得两张图对应的边的颜色是一样的，我们就称这两张有色图是同构的。以下两张图就是同构的，因为假如你把第一张图的顶点 \((1,2,3,4)\) 置换成第二张图的 \((4,3,2,1)\)，就会发现它们是一样的。

你的任务是，对于计算所有顶点数为 \(n\)，颜色种类不超过 \(m\) 的图，最多有几张是两两不同构的图。由于最后的答案会很大，你只要输出结论模 \(p\) 的余数就可以了（\(p\) 是一个质数）。

输入格式：

输入文件只有一行，由三个正整数 \(n,m,p\) 组成。

输出格式：

即总数模 \(p\) 后的余数。

数据范围：

\(1\leq n\leq 53\)，\(1\leq m\leq 1000\)，\(n<p\leq 10^9\)。

本题读完就能看出来是在考察 Burnside 引理/Pólya 定理，不过这都是 06 年的题了。

题目要求的是对于点的 \(n!\) 种置换，本质不同的染色方案有多少种。

Burnside 引理（用于求解一些本质不同的计数问题）

设 \(A,B\) 为有限集合，\(X\) 为一些从 \(A\) 到 \(B\) 的映射组成的集合。

\(G\) 是 \(A\) 上的置换群，且 \(X\) 中的映射在 \(G\) 中的置换作用下封闭。

\(X / G\) 表示 \(G\) 作用在 \(X\) 上产生的所有等价类的集合，则 \[ |X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^g\right| \] 其中 \(X^g=\{x \mid x \in X,~g(x)=x\}\) ，表示置换 \(g\) 作用下的不动点的集合。

在本题中

\(A\) 是所有边的集合，\(B\) 是所有颜色的集合
\(X\) 是对每条边染色的方案的集合，\(G\) 是 \(A\) 上的置换群

考虑一个点的置换 \(\varphi = \binom{a_1, a_2, \ldots, a_n}{a_{p_1}, a_{p_2}, \ldots, a_{p_n}}\) ，根据置换的性质，

我们可以将其拆成 \(k\) 个长度为 \(b_1,b_2,\cdots,b_k\) 的不相交的循环置换的乘积。

那么 \(\varphi\) 作用下的不动点的个数为 \(m\) 的「在这个置换作用下，边的等价类个数」次方

那么怎么计算这个边的等价类的个数呢？（注意，到目前为止没有用到 Pólya 定理，不要混淆了）

考虑将边分为两类，分别是端点在同一循环置换中的边，和不在同一循环置换中的（以下简称循环）

在同一循环内的边，设该循环长 \(b\) ，将这 \(b\) 个点按顺序等距分布在一个圆上

在循环的作用下每条边都会逆时针旋转一格，显然两条边处于不同的等价类当且仅当他们长度不同。

可以得出长度为 \(b\) 的循环内部共有 \(\left\lfloor\frac{b}{2}\right\rfloor\) 种边的等价类（正多边形的性质，其实画一下就知道了）。

下图是 \(b=6\) 的情况。
不在同一循环内的边，考虑两个长度为 \(b_1,b_2\) 的循环。

对于一条边，在这个置换的重复作用下经过 \(\operatorname{lcm}(b_1,b_2)\) 次操作会回到自身

因此每条边在一个大小为 \(\mathrm{lcm}(b_1,b_2)\) 的等价类中，则不同等价类的个数为 \(\frac{b_1b_2}{\mathrm{lcm}(b_1,b_2)}=\gcd(b_1,b_2)\) 。

下图是 \(b_1=3,b_2=2\) 的情况，对应循环 \((1,2,3)\) 和 \((4,5)\) 。

（上面这部分可能比较难理解，需要多思考一下）

因此在当前置换下边的等价类的个数为 \[ |X^{\varphi}| = \sum_i\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i<j} \operatorname{gcd}\left(b_i, b_j\right) \] 对于一个求出了 \(b\) 的置换，我们可以在 \(\mathcal{O}(k^2 \log b_i)\) 的复杂度内求出。

接着考虑对所有置换统计。当然不可能直接枚举置换 \(\varphi\) ，注意到 \(b\) 一样的 \(\varphi\) 答案相同

考虑枚举 \(b\) ，即本质不同的不相交循环置换长度的可重集，这相当于对 \(n\) 整数划分

不妨钦定 \(b_1 \le b_2 \le \cdots \le b_k\) ，其中 \(\sum b_i=n\) ，考察其对应的置换 \(\varphi\) 的个数。

考虑 \(1\) 到 \(n\) 的每个点，将其分配到若干个子集中，这相当于多重组合数 \[ \binom{n}{b_1,b_2\cdots,b_k} = \frac{n!}{b_1!b_2!\cdots b_k!} \] 而子集的内部顺序相当于一个圆排列，直接算是 \(\prod (b_i-1)!\) ，乘上之前的就是 \[ \frac{n!}{\prod b_i} \] 但实际上这样会算重，因为当 \(b_i\) 相同时，循环的前后顺序会导致答案算重（比如 \((1,2)(3,4)\) 和 \((3,4)(1,2)\) ）

设有 \(c_j\) 个 \(b_i\) 相同，每次相同都会多乘 \(c_j!\) ，因此正确的方案数为 \[ \frac{n!}{\prod b_i\prod c_j!} \] 说了这么多总算可以套 Burnside 引理了，因为 \(|G|=n!\) ，所以答案就是 \[ \mathrm{Ans} = \sum_b \frac{1}{\prod b_i \prod c!} \cdot m^{\sum_i\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i<j} \operatorname{gcd}\left(b_i, b_j\right)} \] 后面那一坨的次方可以在枚举 \(b\) 的过程中计算出来。

因此复杂度是 \(\displaystyle \mathcal{O}\left(\log n \sum_{p \in \operatorname{Partition}(n)} \operatorname{len}^2(p)\right)\)

这个东西看上去非常的可怕，其实数量级并不大，而且这里上界有些宽松，参考OEIS A296010

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(66))

int m, p, res, inv[N], fac[N], infac[N];
void add(int &x, int y) { (x += y) >= p ? x -= p : 0; }
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int qpow(int a, int b)
{
    int r = 1;
    for(; b; b >>= 1, a = a * a % p)
        if(b & 1) r = r * a % p;
    return r;
}
int n1, n2 = 1, top, stk[N];
void init(int n)
{
    inv[1] = fac[0] = 1;
    for(int i = 2; i <= n; i++) inv[i] = (p - p / i) * inv[p % i] % p;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p;
    infac[n] = qpow(fac[n], p - 2);
    for(int i = n; i; i--) infac[i - 1] = infac[i] * i % p;
}
void dfs(int s, int mx, int c)
{
    if(!s) return add(res, qpow(m, n1) * n2 % p), void(0);
    int a = n1, b = n2;
    for(int i = 1; i <= mx; --top, i++)
    {
        stk[++top] = i; n1 = a + i / 2;
        for(int j = 1; j < top; j++) n1 += gcd(stk[j], i);
        n2 = b * inv[i] % p;
        if(i == stk[top - 1]) n2 = n2 * fac[c] % p * infac[c + 1] % p;
        dfs(s - i, min(s - i, i), i == stk[top - 1] ? c + 1 : 1);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n >> m >> p; 
    init(n + 5); dfs(n, n, 0); cout << res << '\n';
    return 0;
}