题解 P4128 【[SHOI2006]有色图】
小粉兔
·
·
题解
在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/10358520.html。
计数好题，原来是 13 年前就出现了经典套路啊。这题在当年应该很难吧。
题意简述：
本质不同指的是在点的 $n!$ 种不同置换下不同。
### 题解：
首先有 $\mathrm{Burnside}$ 引理：一类元素在一个**置换群**的作用下本质不同的元素（不同等价类）个数等于 $\displaystyle\frac{1}{|G|}\sum_{g\in G}M(g)$。其中 $G$ 是所有置换的集合，$M(g)$ 是一个置换的不动点个数。
那么我们考虑一个点的置换 $(a_1,a_2,\ldots,a_n)$，因为一个置换可以拆分成不相交循环的乘积，考虑这个置换能拆分成 $k$ 个长度分别为 $b_1,b_2,\ldots,b_k$ 的不相交循环的乘积。显然它的不动点个数为 $m$ 的在这个置换下边的等价类个数次方。如何计算它的边等价类个数？
我们考虑两类边，第一类是端点在同一循环中的边，第二类是端点在不同循环中的边。
对于第一类边，考虑一个长度为 $b$ 的循环。把 $b$ 个点按顺序等距分布在一个圆上，在循环作用下每条边都会往顺时针方向位移一格。则容易得到两条边处于不同等价类当且仅当它们长度不同，可以得出长度为 $b$ 的循环内部共有 $\displaystyle\left\lfloor\frac{b}{2}\right\rfloor$ 种边的等价类。
对于第二类边，考虑两个长度分别为 $b_1$ 和 $b_2$ 的不同循环。对于一条边，在这个置换的重复作用下经过 $\mathrm{lcm}(b_1,b_2)$ 次操作会回到自身。所以每条边的在一个大小为 $\mathrm{lcm}(b_1,b_2)$ 的等价类中，则不同等价类的个数为 $\displaystyle\frac{b_1b_2}{\mathrm{lcm}(b_1,b_2)}=\gcd(b_1,b_2)$。
综合得到等价类个数为 $\displaystyle\sum_{i}\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i<j}\gcd(b_i,b_j)$。对于一个求出了 $b$ 的置换，这个式子可以在 $\Theta(k^2\log b_i)$ 的时间内求出。
接下来需要对所有置换统计，显然我们不能枚举每个置换，但是可以发现，$b$ 一样的置换答案也相同。考虑枚举 $b$，即本质不同的不相交循环长度的可重集。这相当于枚举 $n$ 的每个整数分拆。本题中 $n\le 53$，而 $53$ 的整数分拆数量也不大。
考虑枚举了 $b_1\le b_2\le \cdots\le b_k$，其中 $\displaystyle\sum b_i=n$，如何计算它对应了多少种不同的置换呢？
考虑对于 $1$ 到 $n$ 的每个点，分配它在第几个循环中，这相当于一个多重组合数 $\displaystyle\frac{n!}{\prod b_i!}$。而对于每一个置换，分配它内部的顺序，这相当于一个圆排列，即 $\prod (b_i-1)!$，结合前面是 $\displaystyle\frac{n!}{\prod b_i}$。最后我们会发现这样其实会算重，因为每个循环的前后顺序不影响，不能把 $1,2$ 和 $2,1$（这里表示每个点在第几个循环内）当作不同的循环分配方案。发现只有 $b_i$ 相同的会影响，假设有 $c$ 个，正好多乘了 $c!$ 种方案，除掉就好了。这相当于 $\displaystyle\frac{n!}{\prod b_i\prod c!}$。
发现因为有 $|G|=n!$ 种置换，正好和最后 $\displaystyle\frac{1}{|G|}$ 抵消了，所以最终的式子是：$\displaystyle\sum_{b}\frac{1}{\prod b_i\prod c!}m^{\sum_{i}\lfloor\frac{b_i}{2}\rfloor+\sum_{i<j}\gcd(b_i,b_j)}$。
对于枚举每一种 $b$，可以直接 DFS。而后面两个东西都是能直接在 DFS 过程中计算的，优化常数。
本题很贴心地保证 $p>n$，可以放心求阶乘和阶乘逆元。
时间复杂度大约是 $\displaystyle\mathcal{O}\left(\log n\sum_{p\in\mathrm{Partition}(n)}\mathrm{len}^{2}(p)\right)$，实际比较小，更多可以查看 [A296010](https://oeis.org/A296010)。
```cpp
#include <cstdio>
#include <algorithm>
typedef long long LL;
const int MN = 60;
int N, M, P, Sum;
inline int qPow(int b, int e) {
int a = 1;
for (; e; b = (LL)b * b % P, e >>= 1)
if (e & 1) a = (LL)a * b % P;
return a;
}
int Inv[MN], Fac[MN], iFac[MN];
inline void Init(int N) {
Inv[1] = 1;
for (int i = 2; i <= N; ++i) {
Inv[i] = (LL)(P - P / i) * Inv[P % i] % P;
}
Fac[0] = iFac[0] = 1;
for (int i = 1; i <= N; ++i) {
Fac[i] = (LL)Fac[i - 1] * i % P;
iFac[i] = (LL)iFac[i - 1] * Inv[i] % P;
}
}
int stk[MN], t, n1, n2 = 1;
void DFS(int s, int mx, int c) {
if (!s) {
Sum = (Sum + (LL)qPow(M, n1) * n2) % P;
return ;
}
int a = n1, b = n2;
for (int i = 1; i <= mx; ++i) {
stk[++t] = i;
n1 = a + i / 2;
for (int j = 1; j < t; ++j) n1 += std::__gcd(stk[j], i);
n2 = (LL)b * Inv[i] % P;
if (i == stk[t - 1]) n2 = (LL)n2 * Fac[c] % P * iFac[c + 1] % P;
DFS(s - i, std::min(s - i, i), i == stk[t - 1] ? c + 1 : 1);
--t;
}
}
int main() {
scanf("%d%d%d", &N, &M, &P);
Init(N);
DFS(N, N, 0);
printf("%d\n", Sum);
return 0;
}
```
听说有色图？来了来了！色图在哪里啊？