题目传送门: 洛谷 P4128 https://www.luogu.org/problemnew/solution/P4128 .
计数好题, 原来是 13 年前就出现了经典套路啊. 这题在当年应该很难吧.
题意简述:
\(n\) 个点的完全图, 点没有颜色, 边有 \(m\) 种颜色, 问本质不同的图的数量对质数 \(p>n\) 取模.
本质不同指的是在点的 \(n!\) 种不同置换下不同.
题解:
首先有 \(\mathrm{P\acute{o}lya}\) 定理: 一类元素在一个置换群的作用下本质不同的元素 (不同等价类) 个数等于 \(\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\) 的循环内部共有 \(\lfloor\frac{b}{2}\rfloor\) 种边的等价类.
对于第二类边, 考虑两个长度分别为 \(b_1\) 和 \(b_2\) 的不同循环. 对于一条边, 在这个置换的重复作用下经过 \(\mathrm{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)\).
综合一下, 得到等价类个数为 \(\sum_{i}\lfloor\frac{b_i}{2}\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\), 其中 \(\sum b_i=n\), 如何计算它对应了多少种不同的置换呢?
考虑对于 \(1\) 到 \(n\) 的每个点, 分配它在第几个置换中, 这相当于一个多重组合数 \(\frac{n!}{\prod b_i!}\). 而对于每一个置换, 分配它内部的顺序, 这相当于一个圆排列, 即 \(\prod (b_i-1)!\), 结合前面是 \(\frac{n!}{\prod b_i}\). 最后我们会发现这样其实会算重, 因为每个循环的前后顺序不影响, 不能把 \(1,2\) 和 \(2,1\)(这里表示每个点在第几个循环内)当作不同的循环分配方案. 发现只有 \(b_i\) 相同的会影响, 假设有 \(c\) 个, 正好多乘了 \(c!\) 种方案, 除掉就好了. 这相当于 \(\frac{n!}{\prod b_i\prod c!}\).
发现因为有 \(|G|=n!\) 种置换, 正好和最后 \(\frac{1}{|G|}\) 抵消了, 所以最终的式子是:\(\sum_{b}\frac{\sum_{i}\lfloor\frac{b_i}{2}\rfloor+\sum_{i<j}\gcd(b_i,b_j)}{\prod b_i\prod c!}\).
对于枚举每一种 \(b\), 可以直接 DFS. 而后面两个东西都是能直接在 DFS 过程中计算的, 优化常数.
本题很贴心地保证 \(p>n\), 可以放心求阶乘和阶乘逆元.
时间复杂度大约是 \(O(\log n\sum_{p\in\mathrm{Partition}(n)}\mathrm{len}^{2}(p))\), 实际比较小, 更多可以查看 https://oeis.org/A296010 .
- #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;
- }
听说有色图? 来了来了! 色图在哪里啊?
洛谷 P4128: bzoj 1815: [SHOI2006]有色图
来源: http://www.bubuko.com/infodetail-2948930.html