题解：P8633 [蓝桥杯 2015 国 B] 模型染色

· · 题解

简要题意

对一张 n 个点 m 条边的图进行 k 染色，求本质不同方案数。

题解

看到求本质不同的方案数我们考虑用 polya 定理解决。这里直接放出式子：

|S/T|={1\over|T|}\sum_{g\in T}|N|^{c(g)}

我们现在来分析一下用 polya 定理需要什么东西？首先我们要找出合法的置换群 T，以及每个置换的轮换个数 c(g)。

翻译一下：首先何为合法的 T？考虑 T 作用在 S 上之后得到的 S' 应该与 S 同构，因为若原图存在 (u,v) 那么置换后就会有 (p_u,p_v)，所以满足同构。然后你发现 n 很小于是我们暴力枚举全排列看哪些是合法的，如果合法就计算答案即可。而 c(g) 就是考虑置换的轮换数，这个每次直接扫一遍即可。

时间复杂度考虑全排列有一个 O(n!)，然后判断合法可以接受 O(n^2)，计算答案还有一个 O(n|T|)，最后一共就是 O(n^2\times n!+n|T|)。