洛谷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;
}