BZOJ 1815: [Shoi2006]color 有色图（Polya定理）

时间：2021-12-05 18:43:39

题意

如果一张无向完全图（完全图就是任意两个不同的顶点之间有且仅有一条边相连）的每条边都被染成了一种颜色，我们就称这种图为有色图。

如果两张有色图有相同数量的顶点，而且经过某种顶点编号的重排，能够使得两张图对应的边的颜色是一样的，我们就称这两张有色图是同构的。

对于计算所有顶点数为 \(n\) ，颜色种类不超过 \(m\) 的图，最多有几张是两两不同构的图。

数据范围

\(n \le 53, 1 \le m \le 1000\)

题解

神仙题qwq

我们考虑对于点置换与其对应的边置换的关系：

  1. 对于不处在循环中的点对：

    假设第一个循环长度为 \(l_1\) 第二个循环长度为 \(l_2\) ，那么循环节长度就是 \(\mathrm{lcm}(l_1, l_2)\) 。

    一共有 \(l_1\times l_2\) 对点对，每个点对所处的循环节长度都是一样的，那么循环节个数就是 \(\displaystyle \frac{l_1l_2}{\mathrm{lcm}(l_1, l_2)} = \gcd(l_1, l_2)\) 。

  2. 对于处在循环中的点对：

    设循环长度为 \(l\) ，分奇偶讨论。

    • \(l\) 为奇数，那么循环长度刚好是 \(l\) ，一共有 \(\displaystyle {l \choose2}\) 对点对，那么刚好就有 \(\displaystyle \frac{l - 1}2\) 个循环节。
    • \(l\) 为偶数，上面那种情况之外，还有转 \(\displaystyle \frac l2\) 长度对应的循环节，那么一共有 \(\displaystyle\frac{ {l \choose 2} - \frac l2}{l} + 1 = \frac l2\) 个循环节。

设一开始点置换划分的周期为 \(l_1 \le l_2 \le \cdots \le l_k\) ，其中满足 \(\sum\limits _{i = 1}^{k} l_i = n\) 。

那么循环节的个数其实就是：

\[\sum_{i = 1}^{k} \lfloor \frac{l_i}{2} \rfloor + \sum_{i = 1}^{k} \sum_{j = i + 1}^{k} \gcd(l_i, l_j)
\]

我们显然可以枚举所有 \(l\) 的集合，不难发现这就是整数划分，\(53\) 的划分数并不大。。。

只剩下最后一个问题，就是有多少个长为 \(n\) 的排列对应到 \(l_1 \cdots l_k\) 这个点置换循环。

首先考虑可重排列计数，把 \(n\) 个数分给这些的方案为 \(\displaystyle \frac{n!}{\prod_{i=1}^{k} l_i!}\) 然后对于每个置换 \(i\) 内部是个圆排列，顺序有 \((l_i - 1)!\) 。然后循环的先后顺序是互不影响的，要除掉 \(c_i! (c_i = \sum_{j = 1}^{n}[l_j = i])\) 个。

也就是

\[\frac{n!}{\prod_{i = 1}^{k}l_i \prod_{i = 1}^{k}c_i!}
\]

总结

对于 \(Polya\) 定理，常常要找循环节个数。对于特殊的置换，我们常常可以利用循环长度是一样的性质，然后用总元素 \(/\) 循环长度，得到循环节个数。

代码

#include <bits/stdc++.h>

#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)

#define Set(a, v) memset(a, v, sizeof(a))

#define Cpy(a, b) memcpy(a, b, sizeof(a))

#define debug(x) cout << #x << ": " << (x) << endl

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {

	int x(0), sgn(1); char ch(getchar());

	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;

	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);

	return x * sgn;

}

void File() {

#ifdef zjp_shadow

	freopen ("1815.in", "r", stdin);

	freopen ("1815.out", "w", stdout);

#endif

}

const int N = 65;

int n, m, Mod;

int cir[N], len, ans = 0;

inline int fpm(int x, int power) {

	int res = 1;

	for (; power; power >>= 1, x = 1ll * x * x % Mod)

		if (power & 1) res = 1ll * res * x % Mod;

	return res;

}

void Dfs(int cur, int rest, int res) {

	if (!rest) {

		int coef = 1, cnt = 1;

		For (i, 1, len) {

			if (cir[i] != cir[i - 1]) cnt = 1; else ++ cnt;

			coef = 1ll * coef * cnt % Mod * cir[i] % Mod;

		}

		ans = (ans + 1ll * fpm(m, res) * fpm(coef, Mod - 2)) % Mod; return;

	}

	For (i, cur, rest) {

		int tmp = i / 2; For (j, 1, len) tmp += __gcd(i, cir[j]);

		cir[++ len] = i; Dfs(i, rest - i, res + tmp); -- len;

	}

}

int main () {

	File();

	n = read(); m = read(); Mod = read();

	Dfs(1, n, 0);

	printf ("%d\n", ans);

	return 0;

}

相关文章