20200903 专题：Polya

总览：

常常用到 Polya定理 来解决计数问题

首先先引入置换群 ,置换简单来说就是对元素进行重排列，即 $[1,n]$ 到 $[1,n]$ 的映射。 循环节就是映射中环的个数

一种写法： $\sigma =(1,3)(2,5)(4)$ 循环节为 3

Polya定理： $$M=\frac{1}{G}\sum _{k=1}^G{m}^{c(\sigma k)}$$ $G$ 为存在的置换群个数 枚举所有置换群 $m$ 为颜色总数 $c(\sigma k)$ 为当前置换群的循环节个数

例： 使用黑白两种颜色对下面的方格进行染色 , 如果允许方格可以绕中心点旋转, 问有多少种不同的着色方案数 ？ 先标号 方格可以旋转 $0°,90°,180°,270°$ 存在 4 个置换群 分别为 $$\begin{gathered} G_1=(1)(2)(3)(4) \\ {G}_2=(1,2,3,4) \\ {G}_3=(1,3)(2,4) \\ {G}_4=(1,2,3,4) \end{gathered}$$ 带入 Polya定理 $M=\frac{1}{4}(2^4+2^1+2^2+2^1)=6$

T1 Necklace of Beads

思路： 一句话题意：给出三种颜色红绿蓝，对一串 n 个小球的环染色，环可以旋转和翻转，问最终可能有多少不同的染色方案。

先考虑旋转 旋转距离可以为 $[0,n-1]$ 个球 旋转距离 k 时，循环节个数为 $gcd(n,k)$

旋转回到自己的最短距离为 $lcm(n,k)$ 此时与它在一个循环节的球数为 $\frac{lcm(n,k)}{k}$ 循环节个数为 $\frac{n}{\frac{lcm(n,k)}{k}}=\frac{nk}{lcm(n,k)}=gcd(n,k)$

再考虑翻转 分总球数为奇偶考虑

总球数为奇数 以每个球为对称轴翻转，共有 $n$ 个置换群 对于每个置换群，循环节个数为 $\frac{n}{2}+1$总球数为偶数 以每个球为对称轴翻转，共有 $\frac{n}{2}$ 个置换群 对于每个置换群，循环节个数为 $\frac{n}{2}+1$ 以每两个球中点为对称轴翻转，共有 $\frac{n}{2}$ 个置换群 对于每个置换群，循环节个数为 $\frac{n}{2}$

最后代入 Polya定理 即可

代码：

#include <bits/stdc++.h> using namespace std; #define LL long long #define re register #define int long long namespace IO { char _buf_[1 << 21], *_p1_ = _buf_, *_p2_ = _buf_; #define ch() \ (_p1_ == _p2_ && (_p2_ = (_p1_ = _buf_) + fread(_buf_, 1, 1 << 21, stdin), \ _p1_ == _p2_) \ ? EOF \ : *_p1_++) inline LL in() { LL s = 0, f = 1; char x = ch(); while (x < '0' || x > '9') { if (x == '-') f = -1; x = ch(); } while (x >= '0' && x <= '9') { s = (s * 10) + (x & 15); x = ch(); } return f == 1 ? s : -s; } char _buf[1 << 21]; int _p1 = -1; inline void flush() { fwrite(_buf, 1, _p1 + 1, stdout); _p1 = -1; } inline void pc(char x) { if (_p1 == (1 << 21) - 1) flush(); _buf[++_p1] = x; } inline void out(LL x) { char k[30]; int pos = 0; if (!x) { pc('0'); return; } if (x < 0) { pc('-'); x = -x; } while (x) { k[++pos] = (x % 10) | 48; x /= 10; } for (int i = pos; i; i--) pc(k[i]); return; } inline void out(string x) { int len = x.size(); for (int i = 0; i < len; i++) pc(x[i]); } } // namespace IO using namespace IO; int n; inline int gcd(int x, int y) { return !y ? x : gcd(y, x % y); } inline int power(int s, int c) { int ans = 1; for (; c; s = s * s, c >>= 1) if (c & 1) ans = ans * s; return ans; } signed main() { n = in(); while (n != -1) { if (!n) { out("0\n"); n = in(); continue; } int res = 0; for (int i = 0; i < n; i++) res += power(3, !i ? n : gcd(n, i)); if (n % 2 == 0) { res += power(3, n / 2 + 1) * n / 2; res += power(3, n / 2) * n / 2; } else res += power(3, n / 2 + 1) * n; res /= (2 * n); out(res), pc('\n'); n = in(); } flush(); return 0; }