前言：若您手中有一本《組合數學》，那麼請翻到P330看書吧，書上講的是真的好。本文也基本參考該書講解】
本篇部落格算是後期兩周内會寫的一篇關于Polya定理的專題的前置知識】
目錄
一、置換
1、定義
2、合成運算
3、置換群
二、置換快速幂運算
1、一般情況
2、互質的時候
3、洛谷P2227 [HNOI2001] 洗牌機
一、置換
1、定義
【描述可能不那麼嚴謹】我們假設有映射函數
，對1~n中的每個數都唯一對應1~n中的某個數，并且每個數都被唯一對應，是滿射。為了更加清楚地表示這一映射關系，我們用一個2*n的陣型來表示：
這樣的映射關系就是置換。舉個例子：對于n=3的時候，有以下6種置換：
2、合成運算
設有置換：
，那麼兩個置換的合成運算就是：
兩兩上下對應交換位置即可。這就是置換的合成運算。
并且我們可以發現：
這一點要特别注意。
同時，我們也經常用幂次來表示自身置換的次數。比如：置換
。
3、置換群【這個跟Polya定理關系比較大
通過前面的講解，我們已經明白了置換的含義。那麼置換群呢？【下文參考《組合數學，其實建議看書會好了解一些】
我們定義
的所n！個置換構成的集合為
。如果
中的置換的非空子集
滿足一下三條性質，則
為
的置換群：
1）封閉性：對于G中的所有置換f與g，
也必定在集合中。
2）機關元：
中的恒等置換屬于G。即G包含恒等置換
。
3）逆元的封閉性：對于G中的每一個置換f，
也屬于G。這一點可以根據置換有循環這一點來判定。
這幾個性質的判定其實不會很難，往往一個置換所有階的置換就是一個置換群。
二、置換快速幂運算【參考潘震皓的講義
1、一般情況
設有置換
【這是輪換形式】，那麼就有：
對于這個結果，我們可以将它寫成輪換形式，也就是從1~6對每個數都走一遍上下對應的輪換：
【2對應5,5對應3,3對應2，這就是一組循環。1,4,6同理.循環内部順序可以打亂
同理，我們得到T的幾個幂次的輪換：【建議手推哦OuO
可以發現一件事情：對于
，輪換形式下，循環的個數就是
，并且【每個循環】分别是T中的下标
的元素組成。
我們繼續輪換下去，還可以發現：
。是以一定有：
【-1和+1是應付下标從0開始這一點，後面置換群還會提到。
2、互質的時候
我們繼續看，會發現一些特殊的情況：當
的時候，結果一定會是一個大循環對吧？那麼如何快速得到這個循環呢？
我們可以再看兩個實驗【其實從這裡開始基本上都是在搬人家講義的内容了QuQ】
設
，則：
其中，
是把其奇數項取出來，再接上偶數項，
是取出mod3為1,2,0的項……
是以就可以得到一個定理：令數組
，并且有
則：
看起來有點複雜。但是可以畫個環了解了解。【原圖來自潘震皓的講義】
注意，這樣一種行走方式是對于輪換形式的，如果我們要求兩個置換，那麼一定要先轉換成輪換形式，這樣早做過後再逆變換回來。逆變換的方式可以自己手推一下。
這個東西有什麼用呢？放個很經典的例題：
洛谷P2227 [HNOI2001] 洗牌機
題解
很顯然，每一次洗牌就是一次置換的合成操作。一共洗s次牌，就相當于給你
的置換狀态，讓你求
的置換狀态。
首先題目保證了n是奇數，我們的指數又一定是2的幂次，是以保證了兩者互質，我們就可以直接套用上面的那個輪換形式下的遞推公式啦。
但是明顯我們不能直接跑2^s這麼多次。是以我們要降低指數。通過對置換群的了解，我們完全可以将指數對n取餘。
代碼很短的，直接看吧。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 1005
using namespace std;
typedef long long ll;
int read() {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x * f;
}
int n, s, a[maxn], b[maxn];
signed main() {
n = read(), s = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1, j = 1; i <= n; i++, j = a[j]) b[i] = a[j];//現在b裡面是a的輪換形式
register int k = 1;
for(int i = 1; i <= s; i++) k = k * 2 % n;//看到底要多少次幂，即走多少步
for(int i = 1, j = 1; i <= n; i++, j = (j + k - 1) % n + 1) a[j] = b[i];//這裡是在走那個圈圈
for(int i = 2, j = a[1]; i <= n + 1; i++, j = b[j]) b[j] = a[(i - 1) % n + 1];//反輪換形式
for(int i = 1; i <= n; i++) printf("%d ", b[i]);
return 0;
}
呼……群論真的是一個很大的知識點啊。關于單純置換的題目還有一個：洛谷P4161 [SCOI2009] 遊戲
迎評：）
——End——