0. 前言

抽象代数警告！
你需要有：

集合论芝士
一颗清醒不头痛的大脑

1. 群

1.1 群的定义

设 $G$ 是非空集合，其上有二元运算 $\times$ （这不是单纯的乘号，这里是抽象代数你应当有这种意识）。若这个运算满足以下四个性质，我们称其为一个群，记为： $(G,\times)$ 。

封闭性

若存在 $a$ 和 $b$ 满足 $a\in G,b\in G$ ，则有 $a\times b \in G$ 。

结合律

对于任意 $a,b,c \in G,\text{有}(a\times b)\times c=a\times (b\times c)$ 。

单位元

$\exists e\in G$ ，满足对于任意 $a\in G$ ，有： $a\times e=e\times a=a$ 。
这样的 $e$ 称为单位元，并且单位元唯一（如果有多个很容易看出来矛盾）

逆元

对于任意 $a\in G$ ，存在 $a'\in G$ ，满足 $a\times a'=a'\times a=e$ 。
$a'$ 也是唯一的。

举个例子，我们比如说实数域上的乘法法则就构成一个群，模意义下的乘法（除0以外）同样是一个群，单位元 $e=1$ 。

（推论）消去律：对于 $a,b,c\in G$ ，如果 $a\times c=b\times c$ 或 $c\times a=c\times b$ ，那么有 $a=b$ 。

还有一些举例，正整数在加法下不够成群，因为正整数没有加法单位元（应为0但是正整数），整数在乘法下不构成群，2整数范围没有乘法逆元。

1.2 子群

如果 $H$ 为 $G$ 的一个子集并且 $(H,\times)$ 构成一个群，那么称 $(H,\times)$ 为 $(G,\times)$ 的子群，简记为 $H\le G$ （这么记是因为子集包括 $G$ ）。

如果 $G$ 是一个群，且 $H$ 是 $G$ 的子群，且 $g\in G$ ，那么：

$gH=g\times h,h\in H$ ，称其为 $H$ 在 $G$ 内关于 $g$ 的左陪集。
$Hg=h\times g,h\in H$ ，称其为 $H$ 在 $G$ 内关于 $g$ 的右陪集。

为什么要这么分呢，看上面的性质，我们没有提到交换律，所以这种算数系统交换过来的结果不一定相同，所以我们需要特别规定。

配集的性质（这里只讨论右配集）：

$\forall g\in G,|H|=|Hg|$ 。

根据逆元唯一，那么对于任意的 $g\times h_{1},g\times h_2$ ，一定必然不同。

$\forall g\in G,g\in Hg$ 。

单位元 $e\in Hg$ ，证毕。

$Hg=H \Leftrightarrow g\in H$ 。

封闭性即得。

$Ha=Hb \Leftrightarrow a\times b^{-1}\in H$

根据陪集运算和逆元可以证明。

$Ha \cap Hb \ne \varnothing \Leftrightarrow Ha=Hb$ 。

这个性质很有用，这说明陪集的交集要么是空集么两个相同。

$H$ 的全体右陪集并为 $G$ 。
显然？因为 $H$ 有单位元。

拉格朗日定理：

对于有限群 $G$ 与有限群 $H$ ，若 $H$ 为 $G$ 的子群，那么有：

|H|\text{ 整除 } |G|

1.3 群作用

我们对于一个集合 $M$ 和群 $G$ 。

若给定二元函数 $\mu(a,b)$ ，其中 $a\in G,b\in M$ ，并且：

\begin{aligned} \mu(e,k)& =k & \text{e为单位元} \\ \mu(g,\mu(s,k)) & = \mu(g\times s,k) & g,s\in G,k\in M \end{aligned}

那么我们就称 $G$ 作用于集合 $M$ 。
理解的来说其实就是把 $G$ 的运算法则给融合进集合 $M$ 了。

2. 置换

定义：一个集合 $X$ 到自身的双射（一一对应） $\sigma$ 称为 $X$ 的一个置换。

2.1 置换的表示

双行表示法，即用两个括号扩起来，令元素从上面一行 “置换” 到下面一行，这个置换就可以用两行来表示。例如下面：

\sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{pmatrix}

这个意思将排列 $1,2,3,4,5$ 变为 $2,3,1,5,4$ 的一个置换，可以理解就是用原本第二个代替第一个，第三个代替第二个，以此类推。

单行表示法，就是把置换后的结果表示出来如下：

\sigma=(a_1,a_2,...a_n)

例如： $\sigma=(2,3,1,5,4)$ 。

我们还有轮换表示，但是我看不懂。

一个长度为 $n$ 的不同置换的个数为 $n!$ ，这个很重要！

2.2 置换的运算

很简单，其实就是 $\sigma \times a$ ，或者更一般的写作 $\sigma(a)$ 。

运算规则就是： $\sigma(a)=(a_{\sigma_1},a_{\sigma_2},....,a_{\sigma_n})$ 。

还是例如上面的数列 $a=(1,2,3,4,5)$ ，那么 $\sigma(a)=(2,3,1,5,4)$ 。

我们称这个运算叫做置换的「合成」。

2.3 置换群

我们不妨设集合 $N=\left\{ 1,2,3,...,n \right\}$ ，令集合 $M$ 为 $N$ 的若干个排列所构成的集合，我们令群 $G=(M,\times)$ ，其中这个 $\times$ 运算即为上面提到的置换的「合成」，若在此基础上，如果满足群的性质我们称 $G$ 为一个置换群。

我们验证上面提到 $M$ 是否和置换合成满足群的性质：

封闭性：显然置换不可能出来新元素。
单位元 $e$ ：显然 $\sigma \times e=e\times \sigma=\sigma$ 。
结合律：容易验证。
逆元：容易构造并验证。

3. 轨道-稳定子定理

3.1 轨道与稳定子

我们设一个作用在集合 $M$ 上的群 $G$ 。 $M$ 中的一个元素 $x$ 的轨道就是通过 $G$ 中的元素可以到达的元素的集合。 $x$ 的轨道被记为 $G(x)$ 。

G(x)=\left\{ g \times x | g\in G \right\}

轨道是 $M$ 的一个子集，表示 $x$ 在群作用下的“运动范围”。

稳定子指的是 $G$ 中固定 $x$ 的元素组成的子群，用 $G^x$ 表示：

G^x=\left\{ g\times x=x| g\in G \right\}

稳定子是 $G$ 的子群，表示那些不改变 $x$ 的群元素。

咱们举个例子，比如说旋转正方形。

我们就定义 $G$ 为旋转操作。

G=\left\{ \text{旋转0°},\text{旋转90°},\text{旋转180°},\text{旋转270°} \right\}

不妨令集合 $M$ 为正方形四个顶点。

M=\left\{ A,B,C,D \right\}

我们选顶点 $x=A$ ，那么它的轨道根据上面不难推出：

0度：A->A
90度：A->B
180度：A->C
270度：A->D
那么 $G(A)=4$ 。稳定子显然转0度才是固定的，所以 $G^A =1$ 。

3.2 轨道-稳定子定理

对于有限群 $G$ 作用与集合上 $X$ 上，定理指出：

|G|=|G^x|\cdot |G(x)|

还是上面的例子，根据上面发现 $4\times 1=4=|G|$ 。

为什么是对的？

根据上面我们提到的拉格朗日定理，那么根据上面提到的 $G^x$ 是 $G$ 子群结论，有：

|G^x|\text{ 整除 } |G|

现在只需要证明 $G(x)$ 是上面的 “除数” 即可。

考虑群 $G$ 在轨道上的作用。对于任意 $g \in G$ ，我们定理映射：

g\cdot x \rightarrow gG(x)

其中 $G(x)$ 仍为稳定子，轨道中的每个点 $g\cdot x$ 对应 $G$ 的一个左陪集 $gG(x)$ ，这个显然可以证明。

那么 $\frac{G}{G(x)}$ 表示 $G$ 所有左配集的集合，这个显然可证明，那就证明完了。

4. Burnside定理与Polya定理

定义 $G$ 为一个群，定义其作用于 $X$ ，轨道的个数等于群中每个元素对应置换的不动点的平均个数，即：

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

证明即：

\begin{aligned} |X/G|& =\sum\limits_{p\in X/G} 1 \\ |X/G| & = \sum\limits_{x\in X}\frac{1}{|Gx|} \\ |X/G|&=\frac{1}{|G|}\sum\limits_{g\in G} |X^g| \end{aligned}

Polya定理是Burnside定理的推论。

对于其中那个不动点解释，并不是要求每个顶点位置都不变，而是要求 “颜色” 分布整体不变，顶点可以移动但是整体的 “颜色” 排列看起来和原来一样

给定群 $G$ 在集合 $X$ 上的作用和颜色集合 $C$ ，则不同的染色方案数目为：

|C^X/G|=\frac{1}{|G|}\sum\limits_{g\in G} m^{c(g)}

其中， $m$ 为颜色数目， $c(g)$ 是元素 $g\in G$ 的置换表示的轮换分解中的轮换数目。

我们啥时候用这个定理，要求比如说计数，并且出现关键词本质不同。

4.1 小练习热身

用红绿蓝（RGB）三个颜色给 3 个顶点的环染色，求本质不同的方案数（旋转对称）。

首先这环旋转肯定构成一个置换群（如果你想用 Burnside 定理，你的前提这个得构成一个置换群！）
我们分类讨论一下。

旋转0度：瞎染色反正不动： $3^3$ 。
旋转120度：这个包括左旋和右旋，只有三个相同的颜色才能做到旋转后不动，所以即 $3^1=3$ 。
旋转240度：同理 $3$ 。

不动点个数即为 $33$ 。因为就对称群就3个操作，所以本质不同方案数即为：

ans=\frac{1}{|G|}\sum\limits_{g\in G} |X^g|=\frac{33}{3}=11

不难验证 11 个方案本质不同。

4.2 大练习

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

4.2是4.1的严格加强版

根据 burnside定理得到：

Ans=\frac{1}{|G|}\sum\limits_{g\in G} |X^g|

我们考虑将这个环转化成一个置换，我们分类讨论：

若旋转0个点，那么所有集合的点都是不动点，那么数量为： $n^n$ 。
若旋转 $k$ 个点，那么一个点是不动点当且仅当这个点在循环节中循环了 $k$ 次后还能回到原来位置，说明就是长度能够被 $k$ 整除。因为循环的长度能被 $n$ 整除。所以其实就是这个长度 $d\gcd(k,n) \equiv 0 \pmod n$

不难发现有 $gcd(k,n)$ 个循环节，所以不动点集合的大小就是 $gcd(k,n)$ 。

源式即为：

ans=\frac{1}{n}\sum\limits_{k=1}^n n^{gcd(k,n)}

这个怎么做？大力反演！

\begin{aligned} ans&=\frac{1}{n}\sum\limits_{k=1}^n n^{gcd(k,n)} \\ ans &= \frac{1}{n}\sum\limits_{d|n}n^d\times \sum\limits_{k=1}^{n/d}[gcd(k,n)=1] & \text{枚举gcd}\\ ans & =\frac{1}{n}\sum\limits_{d|n}n^d\varphi(\frac{n}{d}) \end{aligned}

注意到本题可以暴力计算欧拉函数，代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr ll MOD=1e9+7;

ll phi(ll n){
    ll ans=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            ans=ans/i*(i-1);
            while (n%i==0)
            {
                n/=i;
            }
        }
    }
    if(n>=2){
        ans=ans/n*(n-1);
    }
    return ans;
}

ll qpow(ll a,ll b){
    ll ret=1;
    while(b){
        if(b&1){
            ret=ret*a%MOD;
        }
        a=a*a%MOD;
        b>>=1;
    }
    return ret%MOD;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        ll n,ans=0;
        cin>>n;
        for(ll i=1;i*i<=n;i++){
            if(n%i!=0) continue;
            ans=(ans+(qpow(n,i)*phi(n/i))%MOD)%MOD;
            if(i*i!=n){
                ans=(ans+qpow(n,n/i)*phi(i)%MOD)%MOD;
            }
        }
        ans=ans*qpow(n,MOD-2)%MOD;
        cout<<ans<<'\n';
    }
    return 0;
}

5.经典大例题

蒟蒻计数太菜了www，有很大一部分都是不会求不动点www。

部分题出自省选集训（原深？启动！）。

5.1 洛谷P1446

不难发现这个洗牌其实就是置换。虽然没说本质不同，但是解释中说明了如果置换后颜色相同那么就说明是相同方案，其实这个代表的就是置换方案。我们后边把 “洗牌” 统一称为 “置换”。

这个置换当然是构成置换群的啦，所以可以搞喽。

考虑用Burnside还是Polya，这个题目限制染色数目了，看来只能用Burnside。

我们公式的 $|G|$ 其实就是 $m+1$ ，但是不动点怎么求？我们考虑原题中说明的，如果置换后仍为原来的颜色集合，那么说明相同。这其实和上面的小大练习有点类似。我们可以知道，我们把一个置换拆成若干个循环置换，这些循环置换对应的位置只能有一种颜色，我们和上面的小大练习算算置换的长度。

设一共有 $tot$ 个循环置换，第 $i$ 个循环置换的长度是 $len_i$ ，这个问题转化为i：把 $len$ 划分成 3 个集合，让三个集合中和分别为 $S_r,S_b,S_g$ 的方案数。这不就是背包问题吗。

设 $f(i,j,k,p)$ 表示对于置换 $g$ ，考虑到第 $i$ 个循环置换，三个集合里的和分别为 $i,j,k$ 的方案数。

边界： $f(0,0,0,0)=1$ .

转移方程如下：

f[0][0][0]=1;
for(int i=1;i<=tot;i++){
    for(int j=sr;j>=0;j--){
        for(int k=sb;k>=0;k--){
            for(int p=sg;p>=0;p--){
                if(j>=siz[i]){
                    f[j][k][p]=(f[j-siz[i]][k][p]+f[j][k][p])%P;
                }
                if(k>=siz[i]){
                    f[j][k][p]=(f[j][k-siz[i]][p]+f[j][k][p])%P;
                }
                if(p>=siz[i]){
                    f[j][k][p]=(f[j][k][p-siz[i]]+f[j][k][p])%P;
                }
            }
        }
    }
}

那么每一个洗牌（置换）都跑一遍记录答案就可以了，于是代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=520;
int sr,sb,sg,n,m,tot,P,f[MN][MN][MN];
int a[MN],siz[MN];
bool vis[MN];

int ksm(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=(ret*a)%P;
        a=(a*a)%P;
        b>>=1;
    }
    return ret;
}

void getring(){
    memset(vis,0,sizeof(vis));
    tot=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            int p=i,len=0;
            while(!vis[p]){
                len++;
                vis[p]=1;
                p=a[p];
            }
            siz[++tot]=len;
        }
    }
}

int clac(){
    memset(f,0,sizeof(f));
    f[0][0][0]=1;
    for(int i=1;i<=tot;i++){
        for(int j=sr;j>=0;j--){
            for(int k=sb;k>=0;k--){
                for(int p=sg;p>=0;p--){
                    if(j>=siz[i]){
                        f[j][k][p]=(f[j-siz[i]][k][p]+f[j][k][p])%P;
                    }
                    if(k>=siz[i]){
                        f[j][k][p]=(f[j][k-siz[i]][p]+f[j][k][p])%P;
                    }
                    if(p>=siz[i]){
                        f[j][k][p]=(f[j][k][p-siz[i]]+f[j][k][p])%P;
                    }
                }
            }
        }
    }
    return f[sr][sb][sg];
}

signed main(){
    int ans=0;
    cin>>sr>>sb>>sg>>m>>P;
    n=sr+sb+sg;
    for(int i=1;i<=n;i++){
        a[i]=i;
    }
    getring();

    // for(int i=1;i<=tot;i++){
    //     cout<<siz[i]<<" ";
    // }
    ans=(ans+clac())%P;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>a[j];
        }
        getring();
        ans=(ans+clac())%P;
    }
    cout<<ans*ksm(m+1,P-2)%P;
    return 0;
}

5.2 洛谷P4128有色图

哪里有色图！
参考AsunderSquall大佬的题解。

如果是点染色，我们可以像上面一样类似的做，但是这里是给边染色，怎么做？我们的Polya定理只能解决点的置换。

我们知道，一个置换其实可以表示成若干个循环，这里我们可以把一个长度为 $n$ 的循环拆成 $m$ 个循环，循环长度分别为 $a_1,a_2...a_m$ 。

因为这里是无标号，我们可以考虑怎样算这样一个拆分对应几个置换。

我们把这些长度当作一个一个区间，往里面填数，但是填数的过程中会发现你填的顺序会造成重复的计算。

注意！以下 $m$ 不是指颜色个数！

我们先把 $n$ 个数随便排列的方案数是 $n!$ 。
因为起点不重要都一样，我们除掉，即除 $\prod\limits_{i=1}^m a_i$
因为两个大小相同的循环相对位置无论怎么放无影响，考虑大小为 $k$ 的循环有 $cnt_k$ 个，排列数为 $cnt_k!$ ，那么还要除掉 $\prod_{k=1} cnt_k$

到这里还是点置换，边置换呢？

考虑一条边，分类讨论：

在循环内，如果循环长度 $k$ 为奇数，一共有 $\binom{k}{2}$ 中可能，一共是 $\frac{k-1}{2}$ 个循环节，所以不动点是 $\frac{k-1}{2}$ 。如果是偶数，除了上面的情况还有一种情况的循环节是 $\frac{k}{2}$ （半个周期并且还是双向边），化简一下出来还是 $\frac{k}{2}$ .综上即为 $\lfloor \frac{k}{2} \rfloor$
不在循环上，考虑两个循环，他们共处在一个 $lcm(k_1,k_2)$ 的循环上（这个也很重要，可以自行搜索），所以一共有 $\frac{k_{1\times}k_2}{lcm(k_1,k_2)}=gcd(k_1,k_2)$ 个循环节，对于分子就是两个循环节能构成多少个点对。综上，不动点共 $gcd(k_1,k_2)$ 个。