（每日一题）P4128 [SHOI2006] 有色图（文末有色图！）（Polya定理）（超级详细，清晰易懂）

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

每日一题（莫反 / 多项式 / 母函数 / 群论） 2021.4.13 群论

嘿嘿嘿，本题题名为 有涩图

文末有色图哦！

P4128 [SHOI2006] 有色图

Weblink

https://www.luogu.com.cn/problem/P4128

Problem

Solution

题目中两个色图相同，当且仅当 $n!$ 的点的排列有相同的边的颜色，也就求本质不同的染色方案数。显然要用Burnside引理或者Polya定理解决。

我们知道任意一种置换都可以表示为若干个不相交的循环置换的乘积，即每个循环置换包含若干个点，总点数为 $n$ 。由于一共只有 $n\le 53$ 个点，我们可以直接暴力 $dfs$ 求一下 $n$ 的拆分数，即将 $n$ 个点拆分为若干个互不相交的循环置换，假设每个循环置换包含的点的个数为 $a_i$，一共 $t$ 个循环置换，则 $\sum _{i=1}^t{a}_i=n$。

如果我们知道 $n$ 个点拆分为若干个循环置换的方案数，根据乘法原理，再乘上用Polya定理计算出来的每个被拆出来的循环置换的本质不同的方案数既是答案。

那么首先计算 $n$ 的拆分数的方案数： 显然 $n$ 个点任意排列的方案数为 $n!$ 。即方案数最多为 $n!$ ，我们再去掉多算的方案数即可。

假设我们拆分为 $t$ 个循环： $a_1,a_2,a_3\cdots ,a_t$（$a_i$ 表示第 $i$ 个循环包含的点的个数）。

首先，我们计算本质不同的时候每一个循环置换在 $n$ 个点中选择的起点不管谁都是同一种方案数（循环置换嘛，起点是谁最后都是一个圈，可以理解为是一个圆排列，旋转同构），所以要要去掉这些多算的方案数，即除掉所有的起点个数的乘积的方案数： $\prod _{i=1}^t\frac{1}{a_i}$ 。

其次，如果两个循环置换的点的个数完全相同的话，他们两个的顺序怎么摆放都是同一种方案，即我们统计一下每一个循环置换的点数为 $x$ 的循环置换个数： $cn{t}_x$，总方案数需要去掉这些方案数，即除掉所有相同循环置换点数的个数之间的排列： $\prod _x\frac{1}{cn{t}_x!}$ 。

综上所诉，将 $n$ 个点拆分为若干个循环置换的总方案数为

$$res=\frac{n!}{\prod _{i=1}^t{a}_i\prod _{x}cn{t}_x!}$$

然后再来分析循环置换本身染色的方案数：

根据Polya定理，对于一个置换 $f$，$C(f)=k^{m(f)}$，其中 $k$ 为颜色数，$m(f)$ 为 $f$ 的循环节。等价类个数（方案数）等于所有置换 $f$ 的 $k^{m(f)}$ 的平均数。

方案数为：

$$N=\frac{{\sum }_{i=0}^{|G|}{k}^{m(f_i)}}{|G|}$$

显然我们一共有 $n!$ 种置换（拆分为 $n!$ 种循环置换），即 $|G|=n!$

故 $$N=\frac{{\sum }_{i=0}^{n!}{k}^{m(f_i)}}{n!}$$

也就是说我们只需要计算一下我们拆分出来的每一个循环置换的不动点的个数 $m(f_i)$ 即可。

我们拆分出 $t$ 个循环： $a_1,a_2,a_3\cdots ,a_t$（$a_i$ 表示第 $i$ 个循环包含的点的个数），假设分别为点集 $(A_1,A_2,\cdots ,A_{a_1}),(B_1,B_2,\cdots ,B_{a_2}),\cdots$

对于在同一个循环内部的点：

显然就是一个旋转同构，即每一个循环置换中的不动点个数为 $\lfloor \frac{a_i}{2}\rfloor$ 个。

对于在不同循环内部的点：

显然就是一个对称同构，即每一个循环置换中的不动点个数为$\sum _{1\le i<j\le m}\gcd (a_i,a_j)$ 。

综上所述，答案 $ans$ 为：

a n s =   r e s × N =   1 ∣ G ∣ × n ! ∏ i = 1 t a i ∏ x c n t x ! k ∑ i = 1 m ⌊ a i 2 ⌋ + ∑ 1 ≤ i < j ≤ m gcd ⁡ ( a i , a j ) =   k ∑ i = 1 m ⌊ a i 2 ⌋ + ∑ 1 ≤ i < j ≤ m gcd ⁡ ( a i , a j ) ∏ i = 1 t a i ∏ x c n t x !

$$\begin{aligned}ans= &\ res\times N \\ =&\ \displaystyle\cfrac{1}{|G|}\times \dfrac{n!}{\prod\limits_{i=1}^t {a_i}\prod\limits_{x}{cnt_x!}} k^{\sum\limits_{i=1}^m\lfloor \cfrac {a_i} 2 \rfloor+\sum\limits_{1\le i<j\le m} \gcd(a_i,a_j)}\\=\ & \displaystyle\dfrac{k^{\sum\limits_{i=1}^m\lfloor \cfrac {a_i} 2 \rfloor+\sum\limits_{1\le i<j\le m} \gcd(a_i,a_j)}}{\prod\limits_{i=1}^t {a_i}\prod\limits_{x}{cnt_x!}}\end{aligned}$$ ans=== ​ res×N ∣G∣1​×i=1∏t​ai​x∏​cntx​!n!​ki=1∑m​⌊2ai​​⌋+1≤i<j≤m∑​gcd(ai​,aj​)i=1∏t​ai​x∏​cntx​!ki=1∑m​⌊2ai​​⌋+1≤i<j≤m∑​gcd(ai​,aj​)​​​

注意不要手贱把 $k^{up}$ 里的 $up$ 膜掉 $mod$ 了，这个最后可以要当作次幂用的啊，应该膜 $mod-1$ ！！！

Code

// Problem: P4128 [SHOI2006] 有色图
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4128
// Memory Limit: 125 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 5e5 + 7;

int n, m, t, mod, cnt, k;
int a[N];
int fact[N], infact[N], inv[N];
int ans;

int qpow(int a, int b)
{
   
	int res = 1;
	while(b) {
   
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

void init(int n)
{
   
	fact[0] = inv[1] = infact[0] = 1;
	for(int i = 2; i <= n; ++ i)
		inv[i] = inv[mod % i] * (mod - mod / i) % mod;
	for(int i = 1; i <= n; ++ i) {
   
		fact[i] = fact[i - 1] * i % mod;
		infact[i] = infact[i - 1] * inv[i] % mod;
	}
}

int up, down = 1;

void dfs(int now, int maxx, int cnt)
{
   
	if(now == 0) {
   
		ans = (ans + qpow(k, up) * down) % mod;
		return ;
	}
	int UP = up, DOWN = down;
	for(int i = 1; i <= maxx; ++ i) {
   
		a[ ++ m] = i;//a[m] = i 就是公式里的 a[i]
		up = (UP + i / 2) % (mod - 1);
		for(int j = 1; j < m; ++ j)
			up += __gcd(a[j], i) % (mod - 1);
		down = (DOWN * inv[i]) % mod;
		if(i == a[m - 1]) {
   //is same
			down = (down * inv[cnt + 1]) % mod;
			dfs(now - i, min(now - i, i), cnt + 1);
		}
		else dfs(now - i, min(now - i, i), 1);
		m -- ;
	}
}

signed main()
{
   
	cin >> n >> k >> mod;
	down = 1;
	init(N - 7);
	dfs(n, n, 0);
	cout << ans << endl;
	return 0;

}

---

你们要的色图：

转载：https://blog.csdn.net/weixin_45697774/article/details/115679401