Pólya 定理學習筆記 | ABC428G 題解

用來對在若干置換下本質不同的方案數計數。

（這里會有一些對引理和定理的證明，但是先咕掉（（

首先是 Burnside 引理：

結論是，假設群 \(G\) 作用于集合 \(X\) 上。

令 \(O_x\) 表示 \(x\in X\) 的軌道，即 \(\{gx|g\in G\}\)。

令 \(X_g\) 表示 \(g\in G\) 的所有不動點，即 \(\{x|x\in X,gx=x\}\)。

Burnsize 引理指出：

\[|\{O_x|x\in X\}|=\dfrac 1{|G|}\sum_{g\in G}|X_g| \]

接下來是 Pólya 定理：

假設群 \(G\) 作用于 \(X\) 上，\(Y\) 是一個有限集，令 \(X^Y\) 是全體映射 \(X\rightarrow Y\) 構成的集合。

（可以認為 \(X\) 是元素，\(Y\) 是顏色, \(X^Y\) 表示所有的染色方案。

定義 \(c(g)\) 表示，取與 \(g\) 等價的置換 \(\sigma_g(x)=gx\)，那么 \(c(x)\) 等于 \(\sigma_g\) 分解成的不相交輪換數量。

那么著名的 Pólya 定理斷言：

\[|\{O_x|x\in X^Y\}|=\dfrac 1{|G|}\sum_{g\in G} |Y|^{c(g)} \]

例題：ABC428G Necklace

權值為 \(v\in[2,n]\) 的珠子有 \(a_v\) 種，每種珠子都有無限個。

對于所有 \(w\in[2,m]\) 求出若干珠子構成的環，權值之積恰好等于 \(w\) 的不同方案數。方案相同當且僅當其僅通過旋轉重合。

\[m\le 5\times 10^5 \]

首先不難發現環長至多為 \(\log m\)。

令 \(f_{i,j}\) 表示，長為 \(i\)，積為 \(j\) 的序列方案數（即不考慮旋轉重合）。

有顯然轉移，

\[f_{i,j} \leftarrow f_{i-1,\frac jv} \times a_v \]

根據 Burnside 引理，有

\[\begin{align*} \text{ans}(w)&=\sum_{k=1}^{\log m}\dfrac 1k\sum_{i=1}^k f_{\gcd(i,k),\sqrt[\frac k{\gcd(i,k)}]{w}} \\&=\sum_{k=1}^{\log m}\dfrac 1k \sum_{d|k} \varphi(\frac kd)f_{d,\sqrt[\frac kd]{w}} \\&=\sum_{k=1}^{\log m}\dfrac 1k \sum_{d|k} \varphi(d)f_{\frac kd,\sqrt[d]{w}} \\&=\sum_{k=1}^{\log m}\sum_{d|k} \dfrac 1k\varphi(d)f_{\frac kd,\sqrt[d]{w}} \\&=\sum_{d=1}^{\log m}\sum_{d|k} \dfrac 1k\varphi(d)f_{\frac kd,\sqrt[d]{w}} \end{align*} \]

注意到當 \(d\ge 2\) 時 \(\sqrt[d]{w}\) 為整數的位置不會很多。

因此復雜度為 \(\mathcal O(m\log m)\)。

Code

#include <iostream>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <vector>
const int N = 5e5 + 7, M = 25;

typedef Modint<998244353> mi;

namespace wyx {

mi phi[M];
class PrimeSieve {
	std::bitset<M> ip;
	std::basic_string<int> pr;
public:
	PrimeSieve(int n) {
		phi[1] = 1;
		for(int i = 2; i < n; ++i) {
			if(!ip[i]) pr += i, phi[i] = i - 1;
			for(int& j: pr) {
				if(i * j >= n) break;
				ip[i * j] = 1;
				if(i % j == 0) {
					phi[i * j] = phi[i] * j;
					break;
				}
				phi[i * j] = phi[i] * (j - 1);
			}
		}	
	}
} PS(M);

struct data { int x, sq, d; };
std::vector<data> g;

int n, m, L, freq[N];
mi dp[M][N], inv[M];
inline void main() {
	std::cin >> n >> m;
	int maxw = 0, minw = 1e9;
	for(int x, i = 1; i <= n; ++i) {
		std::cin >> x, ++freq[x];
		maxw = std::max(maxw, x);
		minw = std::min(minw, x);
	}
	L = std::floor(logl(m) / logl(minw));
	for(int i = 1; i <= L; ++i) inv[i] = mi(i).inv();
	dp[0][1] = 1;
	for(int i = 1; i <= L; ++i) {
		for(int j = minw; j <= maxw; ++j) {
			if(!freq[j]) continue;
			int upbound = m / j;
			for(int k = 1; k <= upbound; ++k) {
				dp[i][k*j] += dp[i-1][k] * freq[j];
			}
		}
	}
	for(int i = 2; 1ll * i * i <= m; ++i) {
		for(i64 j = 2, k = i * i; k <= m; ++j, k *= i) {
			g.push_back(data{(int)k, i, (int)j});
		}
	}
	std::sort(g.begin(), g.end(), [](auto&& x, auto&& y) {
		return x.x > y.x;
	});
	for(int x = 2; x <= m; ++x) {
		mi ans = 0;
		for(int k = 1; k <= L; ++k) {
			ans += inv[k] * phi[1] * dp[k][x];
		}
		while(!g.empty() && g.back().x == x) {
			auto& [__, sq, d] = g.back(); g.pop_back();
			for(int k = d; k <= L; k += d) {
				ans += inv[k] * phi[d] * dp[k / d][sq];
			}
		}
		std::cout << ans << " ";
	}
}

};

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
	wyx::main();
}

例題：P4980【模板】Pólya 定理

求 \(n\) 種顏色給長為 \(n\) 的環染色，僅通過旋轉重合的方案被認為相同，求本質不同方案數，\(n\le 10^9\)。

定義 \(Y=\{C_1,C_2,\cdots,C_n\}\) 表示所有的顏色。

\(X\) 表示環上的 \(n\) 個點表示的集合。

群 \(G=(\{\) 順時針旋轉 \(i\) 個單位 \(| 0\le i < n\},\)操作復合\()\)。

由 Pólya 定理直接得出答案為：

\[\dfrac 1n \sum_{i=1}^nn^{\gcd(i,n)}=\dfrac 1n\sum_{d|n}n^d\varphi(\dfrac nd) \]

posted @ 2025-10-23 22:15 CuteNess 閱讀(11) 評論(0) 收藏舉報

刷新頁面返回頂部

CuteNess

Pólya 定理學習筆記 | ABC428G 題解