Burnside引理和Polya定理 & [bzoj 1004] [HNOI2008]Cards：Burnside引理，動态規劃

題意：有Sr張紅色牌、Sg張綠色牌和Sb張藍色牌，m種洗牌法（置換），兩種牌相同當且僅當一種能洗成另一種，保證洗牌法滿足封閉性、存在逆元，問有多少種染色方案。輸出答案模質數p的結果，Max{Sr,Sb,Sg}<=20，m<=60,m+1<p<100。

Burnside引理用于解決等價類計數問題。

設G是置換群，定義等價關系R：

R={(a,b)|a,b∈Ω,∃f∈G:b=f(a)}

設L是 Ω 中所有等價類，從每一類中任取一進制素構成的集合，則

|L|=∑g∈Gc1(g)|G|

其中 c1(g) 是 g 函數不動點的數目，即g作用其上得到它本身的元素個數。

證明：

設 Zk 是 k 的轉置不動類，Ek是 k 的等價類。

|L|=∑x∈L|Ex||Ex|=∑x∈L∑y∈Ex1|Ey|=∑x∈L∑y∈Ex|Zy||G|=∑x∈Ω|Zx||G|=∑g∈Gc1(g)|G|

其中第三個等号用到這樣一個等式：

|Zk||Ek|=|G|

證明如下：

顯然 Zk 是 G 的子群，由拉格朗日陪集定理知|G|是 |Zk| 的倍數……

子群的陪集是不相交的，如果 f,g 在 Zk 的同一個陪集内，則把它們分到一類，那麼 G 被劃分為一些子集，由陪集的性質，每個子集大小為|Zk|。

設 f=g∘h,g∈G,h∈Zk ，則 f(k)=g(k) ，即一類中的函數作用在 k 上得到同一個元素。顯然這些類與Zk形成一一對應，于是一共有 |Ek| 類。

問賀神這個等式怎麼證，賀神推薦了陪集的概念、拉格朗日定理，于是我腦補了以上幾段。目前也隻能給出這樣叙述不甚嚴謹的證明了QAQ

Polya定理是Burnside引理很顯然的推論。對于一個置換 f ，把它分解為m(f)個循環。 f 的不動點必須使得每個循環内的格子顔色相同。設共有d種顔色，那麼 c1(f)=dm(f) 。Polya定理：等價類的個數等于所有置換 f 的dm(f)的平均數。

學習Burnside引理和Polya定理要明确概念：等價類是 Ω 上的，置換和函數複合運算構成置換群 <G,∘> <script type="math/tex" id="MathJax-Element-178"> </script>。使用它們必須驗證描述等價關系的 G 滿足封閉性、存在機關元和逆元，結合律已由函數複合運算的性質保證。

讓我們來看一看bzoj 1004。由于每種顔色有數目限制，不能直接使用Polya定理的公式，但其思想仍可借鑒。将每種洗牌法分解為循環，每個循環内的格子必須同色。定義狀态為考慮到第幾個循環、每種顔色分别有多少可用，DP即可。四個次元中可以去掉一維顔色，這裡使用記憶化搜尋，事實上沒求解這些無用的狀态。時間複雜度O(mn3)。

題目僅保證封閉性和逆元的存在性，我們需要自己加上機關元。其實還應該驗證一下各個洗牌法互不相同，不過出題人挺良心。

#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_N = , MAX_C = ;
int p, a[MAX_N+], sz[MAX_N+], f[MAX_N+][MAX_C+][MAX_C+][MAX_C+];
bool vis[MAX_N+];

int inv(int x)
{
    int y = ;
    for (int n = p-; n; n >>= ) {
        if (n & )
            y = y*x%p;
        x = x*x%p;
    }
    return y;
}

int dp(int k, int r, int b, int g)
{
    if (k == )
        return ;
    int& x = f[k][r][b][g];
    if (x >= )
        return x;
    x = ;
    if (r >= sz[k])
        x += dp(k-, r-sz[k], b, g);
    if (b >= sz[k])
        x += dp(k-, r, b-sz[k], g);
    if (g >= sz[k])
        x += dp(k-, r, b, g-sz[k]);
    return x %= p;
}

int main()
{
    int sr, sb, sg, m;
    scanf("%d %d %d %d %d", &sr, &sb, &sg, &m, &p);
    int n = sr+sb+sg;
    memset(f, -, sizeof(f));
    for (int i = ; i <= n; ++i)
        sz[i] = ;
    int ans = dp(n, sr, sb, sg);
    for (int k = ; k <= m; ++k) {
        for (int i = ; i <= n; ++i)
            scanf("%d", &a[i]);
        memset(vis, , sizeof(vis));
        int cnt = ;
        for (int i = ; i <= n; ++i) {
            if (vis[i])
                continue;
            vis[i] = true, sz[++cnt] = ;
            for (int j = a[i]; j != i; j = a[j])
                vis[j] = true, ++sz[cnt];
        }
        memset(f, -, sizeof(f));
        ans += dp(cnt, sr, sb, sg);
    }
    printf("%d\n", ans*inv(m+)%p);
    return ;
}