第四节 Pólya定理
|
144
|
0
|
第三章 线性代数

1865 字
|
25 分钟

Contents

Burnside 引理

|X/G|=\frac{1}{|G|}\sum_{g\in G}X^g

其中， X^g 为 X 在 g 作用下的不动点的数量。即满足 g(x)=x 这样的 x 的数量.

文字描述：X 在置换群 G 作用下的等价类总数等于每一个 g 作用于 X 的不动点的算数平均值.

例题

题目：poj2888 Magic Bracelet

题目大意：

一个长度为 N(N\le 10^9) 的环形珍珠项链，有 M(M\le 10) 种颜色，每个珍珠可以任选一种颜色染色，但是规定了 K 对禁止关系 (a,b)，即不能存在颜色分别为 a,b 的珍珠相邻，询问可以有多少种染色方法可以得到本质不同的珍珠项链(通过旋转得到的项链为本质相同)。

解题思路：

考虑 Burnside 引理。观察全部的置换，一共有 N 种：旋转 0,1,2,\cdots ,N-1。做长度为 L 的置换时，注意到循环节长度为 x=\gcd(N, L)，并且每个循环节的染色方案必须相同。因此我们只需考虑长度为 x 的循环节的染色方案数。

  1. 计算循环节的染色方案数：
    考虑矩阵转移，转移矩阵中 f[i][j]=1 当且仅当 i 和 j 可以相邻。考虑初始矩阵，即只能自己到自己，是一个单位矩阵；用矩阵快速幂计算 g=f^x，g[i][j] 即表示从 i 到 j 的方案数。注意到我们实际上求的是一个环上的方案数（下一个循环节的第一位和此循环节的第一位相同），因此取对角线上元素之和即可。

  2. 计算答案
    我们不能暴力枚举全部的 \text{gcd}(N, L)。但是我们可以枚举 [1,\sqrt{n}] 的 \gcd。[1,N] 中，共有 \varphi(N/x) 个数满足 \gcd(N, i)=x。因此我们枚举 N 的全部 \sqrt{N} 以内的约数即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int P = 9973;
int T;
int n,m,k;

struct Mat {
    int n;
    int a[12][12];
    Mat() {}
    Mat(int _n) : n(_n) {
        memset(a, 0, sizeof(a));
    }
    Mat operator * (const Mat &x) const {
        Mat ret;
        ret.n = n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                long long tmp = 0;
                for (int k = 1; k <= n; k++) {
                    tmp += a[i][k] * x.a[k][j];
                }
                ret.a[i][j] = tmp % P;
            }
        }
        return ret;
    }
};
Mat mpow(Mat a, int b) {
    Mat ret(a.n);
    for (int i = 1; i <= a.n; i++) ret.a[i][i] = 1;
    for (; b; b >>= 1, a = a * a) {
        if (b & 1) ret = ret * a;
    }
    return ret;
}

int phi(int x) {
    int ret = x;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) ret = ret / i * (i - 1);
        while (x % i == 0) x /= i;
    }
    if (x > 1) ret = ret / x * (x - 1);
    return ret % P;
}

int ksm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) {
        if (b & 1) ret = 1LL * ret * a % P;
    }
    return ret;
}
int ni(int a) {
    return ksm(a, P - 2);
}

Mat g;

int solve(int d) {
    int ans = 0;
    Mat tmp = g;
    tmp = mpow(tmp, d);
    for (int i = 1; i <= m; i++) {
        ans += tmp.a[i][i];
    }
    return ans % P;
}

int main() {
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        int ans = 0;
        g.n = m;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= m; j++) g.a[i][j] = 1;
        }
        for (int i = 1, a, b; i <= k; i++) {
            scanf("%d%d", &a, &b);
            g.a[a][b] = g.a[b][a] = 0;
        }
        for (int i = 1; i * i <= n; i++) {
            if (n % i) continue;
            if (n / i == i) {
                (ans += (solve(i) * phi(n / i))) %= P;
            }
            else {
                (ans += (solve(i) * phi(n / i))) %= P;
                (ans += (solve(n / i) * phi(i))) %= P;
            }
        }
        ans = ans * ni(n % P) % P;
        printf("%d\n", ans);
    }
    return 0;
}

题目：2019ICPC南昌 J. Summon

题目大意：

一个长度为 n(N\le 10^5) 的环形珍珠项链，有 4 种颜色，每个珍珠可以任选一种颜色染色，但是规定了 m 种禁止关系 (a,b,c,d)，即不能存在颜色为 a,b,c,d 的四元组珍珠相邻，询问可以有多少种染色方法可以得到本质不同的珍珠项链。

解题思路：

和上题类似。考虑长度为 x 的种类数。我们把三个连续的珠子看作是一个状态，类比上题可得到一个 64\times 64 的转移矩阵。注意此矩阵的初始化，不是所有点都可以为 1。

int main(int argc, const char * argv[]) {
    init();
    scanf("%d%d", &n, &m);
    Mat base(64);
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                int x = 4 * (4 * i + j) + k + 1;
                for (int l = 0; l < 4; l++) {
                    int y = 4 * (4 * j + k) + l + 1;
                    base.a[x][y] = 1;
                }
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        int x = 4 * (4 * a + b) + c + 1;
        int y = 4 * (4 * b + c) + d + 1;
        base.a[x][y] = 0;
    }
    long long ans = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i) continue;
        if (n / i == i) {
            (ans += (1LL * solve(i, base) * phi[n / i] % P)) %= P;
        }
        else {
            (ans += (1LL * solve(i, base) * phi[n / i] % P)) %= P;
            (ans += (1LL * solve(n / i, base) * phi[i] % P)) %= P;
        }
    }
    ans = ans * ni(n) % P;
    printf("%lld\n", ans);
    return 0;
}

Pólya定理

如果用 m 种颜色来染色，G 为置换群，g 为其中一个置换，c(g) 为置换 g 的轮换数，则本质不同的染色方案数：

\frac{1}{|G|}\sum_{g\in G}m^{c(g)}

模版题

题目：P4980 【模板】Pólya 定理

题目大意：

给定一个 n 个点，n 条边的环，有 n 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 10^9+7 取模.

分析：

对于旋转 l 的置换，循环个数为 \gcd(l,n)。因此：

\begin{aligned}
ans&=\frac{1}{n}\sum_{i=1}^{n}n^{gcd(n,i)}\cr &=\frac{1}{n}\sum_{d|n}n^d\sum_{i=1}^{n}[gcd(i,n)=d]\cr &=\frac{1}{n}\sum_{d|n}n^d\sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]\cr &=\frac{1}{n}\sum_{d|n}n^d\varphi(\frac{n}{d})
\end{aligned}

可暴力计算欧拉函数。

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
int T, n;

int ksm(int a, int b) {}
int inv(int x) {}
int phi(int x) {}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int ans = 0;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                if (n != i * i) {
                    (ans += 1LL * ksm(n, i) * phi(n/i) % P) %= P;
                    (ans += 1LL * ksm(n, n/i) * phi(i) % P) %= P;
                }
                else (ans += 1LL * ksm(n, i) * phi(n / i) % P) %= P;
            }
        }
        ans = 1LL * ans * inv(n) % P;
        printf("%d\n", ans);
    }
    return 0;
}

应用

题目：sgu208 Toral Tickets

题目大意：

给 N 和 M，对于一个 N\times M 的单面方格纸能对它的每个个格子黑白染色。然后把方格纸的长边卷起来，卷成一个圆柱体，然后再把两个短边形成的圆也接起来。形成一个游泳圈的形状（我们染的色仅仅在游泳圈的外表面）。假设对于两种黑白染色方案。通过卷成这种游泳圈后，是一样的。则这两种方案也是一样的。求染色方案总数。(N,M\le 20)

分析：

分两种情况：

  1. 若 N=M，那么就有翻转 0\degree,90\degree,180\degree,270\degree与上下移动，左右移动共 N\cdot M\cdot 2\cdot 2 种置换；

  2. 若 N\not =M，那么就有翻转 0\degree,1800\degree 与上下移动，左右移动共 N\cdot M\cdot 2 种置换；

分别爆搜出全部置换，再算出每个置换的循环节个数即可。需要用到高精度。

#include <bits/stdc++.h>
using namespace std;

int n, m, s;
bool isEqual, vis[405];
bigint ans, pow2[405];
vector<int> a;

void init() {
    isEqual = (n == m);
    s = n * m;
    a.resize(s);
    for (int i = 0; i < s; i++) a[i] = i;
    pow2[0] = 1;
    for (int i = 1; i <= 400; i++) {
        pow2[i] = pow2[i - 1] + pow2[i - 1];
    }
}

inline int id(int x, int y) {
    return x * m + y;
}

int cal(vector<int> &x) {
    int ret = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < s; i++) {
        if (vis[i]) continue;
        ret++;
        int id = i;
        while (!vis[id]) {
            vis[id] = 1;
            id = x[id];
        }
    }
    return ret;
}

void rotate(vector<int> &x) {
    vector<int> y(x.size());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            y[id(j, n - 1 - i)] = x[id(i, j)];
        }
    }
    x = y;
}

void turnround(vector<int> &x) {
    reverse(x.begin(), x.end());
}

void shiftLeft(vector<int> &x) {
    vector<int> y(x.size());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            y[id(i, j)] = x[id(i, (j + 1) % m)];
        }
    }
    x = y;
}
void shiftDown(vector<int> &x) {
    vector<int> y(x.size());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            y[id(i, j)] = x[id((i + 1) % n, j)];
        }
    }
    x = y;
}

void work() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int = 2;
            while (--) {
                if (isEqual) {
                    rotate(a); ans += pow2[cal(a)];
                    rotate(a); ans += pow2[cal(a)];
                }
                else {
                    turnround(a); ans += pow2[cal(a)];
                }
            }
            shiftLeft(a);
        }
        shiftDown(a);
    }
    if (isEqual) ans /= (s * 4);
    else ans /= (s * 2);
}

int main(int argc, const char * argv[]) {
    scanf("%d%d", &n, &m);
    init(); work();
    cout << ans << endl;
    return 0;
}

题目：2017ICPC青岛 E. Floppy Cube

题目大意：

给一个 3\times 3\times 1 的魔方，然后给 n 个颜色，问有多少种本质不同的魔方。本质相同的魔方是指通过旋转翻转，或者转动一条边，可以变成同一个魔方。

分析：

全部的置换可以分成三种：转动最右边的棱，顺时针旋转 90\degree，整体使魔方翻面。对魔方的 30 个面标号，爆搜出全部不同的置换，分别计算循环节即可。

注意模数不一定是质数，而只有一个除数。我们可以把 a/b \bmod p 转换成 (a \bmod bp)/b，这个在 a 整除 b 的时候满足。

#include <bits/stdc++.h>
using namespace std;

vector<int> ini;
int n, p;

const int change1[30] = {
    0, 1, 17, 3, 4, 14, 6, 7, 11, 9, 10, 8, 12, 13, 5,
    15, 16, 2, 18, 19, 20, 21, 22, 27, 26, 25, 24, 23, 28, 29
};
const int change2[30] = {
    6, 3, 0, 7, 4, 1, 8, 5, 2, 15, 12, 9, 16, 13, 10,
    17, 14, 11, 21, 22, 23, 24, 25, 26, 27, 28, 29, 18, 19, 20
};
const int change3[30] = {
    11, 10, 9, 14, 13, 12, 17, 16, 15, 2, 1, 0, 5, 4, 3,
    8, 7, 6, 26, 25, 24, 23, 22, 21, 20, 19, 18, 29, 28, 27
};

vector< vector<int> > change;
queue< vector<int> > q;
set< vector<int> > s;

vector<int> to(vector<int> &a, vector<int> &change) {
    vector<int> ret(30);
    for (int i = 0; i < 30; i++) {
        ret[i] = change[a[i]];
    }
    return ret;
}

void bfs() {
    vector<int> v = ini;
    q.push(v);
    while (!q.empty()) {
        vector<int> x = q.front();
        q.pop();
        s.insert(x);
        for (int i = 0; i < 3; i++) {
            vector<int> nex = to(x, change[i]);
            if (!s.count(nex)) {
                q.push(nex);
                s.insert(nex);
            }
        }
    }
}

int cnt[35], vis[35];
void work() {
    for (vector<int> x : s) {
        memset(vis, 0, sizeof(vis));
        int tot = 0;
        for (int i = 0; i < 30; i++) {
            if (vis[i]) continue;
            tot++;
            int id = i;
            while (!vis[id]) {
                vis[id] = 1;
                id = x[id];
            }
        }
        cnt[tot]++;
    }
}

void init() {
    vector<int> tmp1(change1, change1 + 30);
    vector<int> tmp2(change2, change2 + 30);
    vector<int> tmp3(change3, change3 + 30);
    change.push_back(tmp1);
    change.push_back(tmp2);
    change.push_back(tmp3);

    ini.resize(30);
    for (int i = 0; i < 30; i++) {
        ini[i] = i;
    }
    bfs();
    work();
}

int main() {
    init();
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &p);
        __int128 ans = 0, beg = 1, P = p * s.size();
        for (int i = 1; i <= 30; i++) {
            (beg *= n) %= P;
            (ans += beg * cnt[i]) %= P;
        }
        ans /= (int)s.size();
        cout << (long long)ans % p << endl;
    }
    return 0;
}
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇