Burnside 定理浅谈

首先说一下文章里面木有证明，主要是通过感性理解的方法能更快地了解这个定理。

我们设置换群为 $G$ 。

轨道稳定集定理

$o r d (x) = g (x), g \in G$ 表示元素 $x$ 在置换中得到的所有元素的集合。
$s t a (x) = g, g \in G, g (x) = x$ 表示对于元素 $x$ 所有将其映射到自身的置换。

我们称 $o r d (x)$ 为 $x$ 的轨道， $s t a (x)$ 为 $x$ 的稳定集。

那么有定理 $| o r d (x) | | s t a (x) | = | G |$ 。

Burnside 定理

我们设

$s_{g} (x) = {\begin{cases} 1, g (x) = x \\ 0, g (x) \neq x \end{cases}$

计数每个 $x$ 不同的轨道数，考虑通过等式进行推出就是：

$\begin{aligned} \sum_{g \in G} \sum_{x \in X} s_{g} (x) & = \sum_{x \in X} \sum_{g \in G} s_{g} (x) \\ = \sum_{x \in X} s t a (x) \\ = \sum_{x \in X} \frac{| G |}{o r d (x)} \\ = | G | \times \sum_{x \in X} \frac{1}{o r d (x)} \\ = | G | \times \sum_{A \in X / G} \sum_{x \in A} \frac{1}{| A |} \\ = | G | \times \sum_{A \in X / G} 1 \\ = | G | \times | X / G | \end{aligned}$

我们将其带入最初的等式得到：

$\begin{aligned} | X / G | & = \sum_{x \in X} \frac{1}{o r d (x)} \\ = \sum_{x \in X} \frac{s t a (x)}{| G |} \\ = \frac{1}{| G |} \sum_{x \in X} s t a (x) \\ = \frac{1}{| G |} \sum_{g \in G} i m m (g) \end{aligned}$

其中 $i m m (g)$ 表示置换 $g$ 的不动点个数。

那么这个就是 $B u r n s i d e$ 定理。

Polya 定理

这个其实就是具体到点的置换上，然后不动点的个数是可以直接计算的。

我们不妨考虑对于所有的点都可以染成 $m$ 中颜色。

对于一个循环 $c i r (g)$ 在循环节里面的部分显然是可以随便染色的。

那么 $| X / G | = \frac{1}{| G |} \sum_{g \in G} m^{c i r (g)}$ 。

这个其实就是该定理。

例题分析

Pólya 定理 - 洛谷

首先发现只有旋转，那么我们构造置换群就是旋转 $0 \to n - 1$ 个的群。

根据 $b u r n s i d e$ 定理可以计算得到答案：

$\sum_{i = 1}^{n} n^{g c d (n, i)}$

我们考虑进行莫比乌斯反演得到最终的式子：

$\sum_{d | n} n^{d} φ (\frac{n}{d})$

时间复杂度 $O (T n^{\frac{3}{4}})$ 。

cpp

#include <bits/stdc++.h>
using namespace std;
namespace Legendgod {
    namespace Read {
//        #define Fread
        #ifdef Fread
        const int Siz = (1 << 21) + 5;
        char *iS, *iT, buf[Siz];
        #define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
        #define getchar gc
        #endif
        template <typename T>
        void r1(T &x) {
            x = 0;
            char c(getchar());
            int f(1);
            for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
            for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
            x *= f;
        }
        template <typename T, typename...Args>
        void r1(T &x, Args&...arg) {
            r1(x), r1(arg...);
        }
        #undef getchar
    }

using namespace Read;

const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int n, m;

int ksm(int x,int mi) {
    int res(1);
    while(mi) {
        if(mi & 1) res = 1ll * res * x % mod;
        mi >>= 1;
        x = 1ll * x * x % mod;
    }
    return res;
}

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

signed main() {
    int i, j, T;
//    printf("%d\n", phi(4));
    r1(T);
    while(T --) {
        r1(n);
        int res(0);
        for(int i = 1; 1ll * i * i <= n; ++ i) if(!(n % i)) {
            res = (res + 1ll * ksm(n, i) * phi(n / i)) % mod;
            if(i * i != n) res = (res + 1ll * ksm(n, n / i) * phi(i)) % mod;
        }
        res = 1ll * res * ksm(n, mod - 2) % mod;
        printf("%d\n", res);
    }
    return 0;
}

}


signed main() { return Legendgod::main(), 0; }

[SHOI2006] 有色图 - 洛谷

考虑通过点置换来计算边，需要使用 $b u r n s i d e$ 定理。

总共点的置换有 $n!$ 种。

对于完全图我们进行旋转，不妨设点数为 $l$ 那么需要进行分类讨论：

$l i s o d d$ ，循环就是 $l$ ，那么贡献的不动点就是总共的边数除以循环，就是 $\frac{l \times (l - 1)}{2 l} = \frac{l - 1}{2}$ 。
$l i s e v e n$ ，除了上述的情况，我们还可以考虑图对称的情况，那么也就是旋转 $\frac{l}{2}$ ，这样当且仅当两点的距离是 $\frac{l}{2}$ 的情况的边才可以满足。也就有 $\frac{\frac{l \times (l - 1)}{2} - \frac{l}{2}}{l} + 1 = \frac{l}{2}$ 。

那么对于同一个循环内的贡献就是 $⌊ \frac{l}{2} ⌋$ 。

我们之后考虑不同循环之间的贡献，也就是在 $l 1, l 2$ 中贡献显然是 $\frac{l 1 \times l 2}{l c m (l 1, l 2)} = g c d (l 1, l 2)$ 。

我们考虑对于所有置换进行暴力搜索枚举，复杂度就是拆分数。但是我们需要考虑对于这样的置换的总数。

考虑每个置换对于总数的贡献，首先总共点数是有 $n!$ ，每个置换内部不会产生贡献，相同长度的置换先后顺序没有贡献。

答案就是 $\frac{n!}{\prod b_{i} \prod l_{i}!}$ 。其中 $l_{i}$ 表示长度为 $i$ 置换的出现次数。

$b_{i}$ 表示第 $i$ 个置换的长度，考虑内部是一个圆排列，本质就是 $\frac{n!}{b_{i}!} \times (b_{i} - 1)!$ 。

cpp

#include <bits/stdc++.h>
using namespace std;
namespace Legendgod {
    namespace Read {
//        #define Fread
        #ifdef Fread
        const int Siz = (1 << 21) + 5;
        char *iS, *iT, buf[Siz];
        #define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
        #define getchar gc
        #endif
        template <typename T>
        void r1(T &x) {
            x = 0;
            char c(getchar());
            int f(1);
            for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
            for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
            x *= f;
        }
        template <typename T, typename...Args>
        void r1(T &x, Args&...arg) {
            r1(x), r1(arg...);
        }
        #undef getchar
    }

using namespace Read;
#define int long long
const int maxn = 2e5 + 5;

int n, m, mod;
int ksm(int x,int mi) {
    int res(1);
    while(mi) {
        if(mi & 1) res = 1ll * res * x % mod;
        mi >>= 1;
        x = 1ll * x * x % mod;
    }
    return res;
}

int gcd(int a,int b) { return b == 0 ? a : gcd(b, a % b); }

int L[maxn], fac[maxn], ans(0);
int vis[maxn];

void Solve(int x) {
    int res(0), mu(1);
    for(int i = 1; i <= x; ++ i) res = (res + (L[i] >> 1)) % (mod - 1);
    for(int i = 1; i <= x; ++ i) {
        for(int j = i + 1; j <= x; ++ j) {
            res = (res + gcd(L[i], L[j])) % (mod - 1);
        }
    }
    for(int i = 1; i <= x; ++ i) mu = 1ll * mu * L[i] % mod;
    L[0] = 0;
    for(int i = 1; i <= x; ++ i) if(L[i] != L[i - 1]) mu = 1ll * mu * fac[vis[L[i]]] % mod;
    mu = 1ll * fac[n] * ksm(mu, mod - 2) % mod;
    ans = (ans + 1ll * mu * ksm(m, res) % mod) % mod;
}

void dfs(int dep,int left,int last) {
    if(left == 0) Solve(dep - 1);
    if(left < last) return ;
    for(int i = last; i <= left; ++ i) {
        L[dep] = i;
        vis[i] ++;
        dfs(dep + 1, left - i, i);
        -- vis[i];
        L[dep] = 0;
    }
}

signed main() {
    int i, j;
    r1(n, m, mod);
//    assert(mod > (int)(1e9));
    fac[0] = 1;
    for(i = 1; i <= n; ++ i) fac[i] = 1ll * fac[i - 1] * i % mod;
    dfs(1, n, 1);
    ans = 1ll * ans * ksm(fac[n], mod - 2) % mod;
    printf("%lld\n", ans);
    return 0;
}

}


signed main() { return Legendgod::main(), 0; }

[HNOI2009]图的同构计数 - 洛谷

这个题目和上一题本质一样，我们需要考虑图出现还是不出现可以变成染成两种颜色。

因为 $n$ 比较大，所以常数需要略微好一点，但是正常都是能过的。

cpp

#include <bits/stdc++.h>
using namespace std;
namespace Legendgod {
    namespace Read {
//        #define Fread
        #ifdef Fread
        const int Siz = (1 << 21) + 5;
        char *iS, *iT, buf[Siz];
        #define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
        #define getchar gc
        #endif
        template <typename T>
        void r1(T &x) {
            x = 0;
            char c(getchar());
            int f(1);
            for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
            for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
            x *= f;
        }
        template <typename T, typename...Args>
        void r1(T &x, Args&...arg) {
            r1(x), r1(arg...);
        }
        #undef getchar
    }

using namespace Read;
#define int long long
const int maxn = 70 + 5;

int n, m, mod;
int ksm(int x,int mi) {
    int res(1);
    while(mi) {
        if(mi & 1) res = 1ll * res * x % mod;
        mi >>= 1;
        x = 1ll * x * x % mod;
    }
    return res;
}

int gcd1(int a,int b) { return b == 0 ? a : gcd1(b, a % b); }

int Gcd[maxn][maxn];

int gcd(int a,int b) { return Gcd[a][b]; }

int L[maxn], fac[maxn], ans(0);
int vis[maxn];

void Solve(int x) {
    int res(0), mu(1);
    for(int i = 1; i <= x; ++ i) res = (res + (L[i] >> 1));
    for(int i = 1; i <= x; ++ i) {
        for(int j = i + 1; j <= x; ++ j) {
            res = (res + gcd(L[i], L[j]));
        }
    }
    res %= mod - 1;
    for(int i = 1; i <= x; ++ i) mu = 1ll * mu * L[i] % mod;
    L[0] = 0;
    for(int i = 1; i <= x; ++ i) if(L[i] != L[i - 1]) mu = 1ll * mu * fac[vis[L[i]]] % mod;
    mu = 1ll * fac[n] * ksm(mu, mod - 2) % mod;
    ans = (ans + 1ll * mu * ksm(m, res) % mod) % mod;
}

void dfs(int dep,int left,int last) {
    if(left == 0) Solve(dep - 1);
    if(left < last) return ;
    for(int i = last; i <= left; ++ i) {
        L[dep] = i;
        vis[i] ++;
        dfs(dep + 1, left - i, i);
        -- vis[i];
        L[dep] = 0;
    }
}

signed main() {
    int i, j;
    r1(n);
    m = 2, mod = 997;
    for(i = 1; i <= n; ++ i) for(j = i; j <= n; ++ j) Gcd[i][j] = Gcd[j][i] = gcd1(i, j);
//    assert(mod > (int)(1e9));
    fac[0] = 1;
    for(i = 1; i <= n; ++ i) fac[i] = 1ll * fac[i - 1] * i % mod;
    dfs(1, n, 1);
    ans = 1ll * ans * ksm(fac[n], mod - 2) % mod;
    printf("%lld\n", ans);
    return 0;
}

}


signed main() { return Legendgod::main(), 0; }

[SDOI2013]项链 - 洛谷

一个恶心的二合一题目。

我们先计算珠子的数量设其为 $m$ 。

那么因为有 $3$ 面，我们考虑合法的三种情况 $s_{3}, s_{2}, s_{1}$ 。

$\begin{aligned} s 3 & = \sum_{i = 1}^{A} \sum_{j = 1}^{A} \sum_{k = 1}^{A} [g c d (i, j, k) == 1] \\ s 2 & = \sum_{i = 1}^{A} \sum_{j = 1}^{A} [g c d (i, j) == 1] \\ s 1 & = 1 \end{aligned}$

简单反演就不说了，之后容斥一下， $m = \frac{s_{3} + 3 s_{2} + 2}{6}$ 。

之后考虑进行计数，但是这里难就在于相邻的两个珠子是不同的。

如果我们知道了 $n$ 个珠子的方案，就是一个 $p o l y a$ 定理。

设其为 $f (n)$ 。

我们考虑两种情况：

这个珠子左右两边的珠子不一样。
这个珠子左右两边的珠子一样。

前者我们可以直接进行转移，因为去掉了当前的珠子还是合法的串，也就是 $f (n - 1) \times (m - 2)$ 。

后者发现去掉了之后是不合法的串，但是如果去掉当前珠子和左右之前任意一个珠子一定是合法的。

考虑形式 $a x y x a z$ 的形式显然去掉了 $x y$ 都是合法的。

然后既然左右两边都是相同的那么肯定是知道了一个珠子的颜色，就是 $f (n - 2) \times (m - 1)$ 。

得到转移方程 $f (n) = f (n - 1) \times (m - 2) + f (n - 2) \times (m - 1)$ 。

考虑进行推通向。

考虑方程 $x^{2} = x (m - 2) + (m - 1)$ 得到 $x = m - 1, - 1$ 。

得到方程：

${\begin{cases} A_{0} x_{0} + A_{1} x_{1} = f (1) \\ A_{0} x_{0}^{2} + A_{1} x_{1}^{2} = f (2) \end{cases}$

解得 $f (n) = (m - 1)^{n} + (- 1)^{n} (m - 1)$ 。

之后还有一点就是不能直接暴力分解质因数，我们考虑将 $n$ 分解质因子之后同样是可以搜索组合出因子，记得求出 $φ$ 。

$φ (d) = \prod_{p^{c}} (p^{c} - p^{c - 1})$

然后注意因为 $n$ 很大可能会被模数整除，我们先让 $n$ 取模模数的平方，之后通过同余方程的性质两边同时除以模数得到答案即可。

需要用到光速乘：

cpp

int64 Mul(int64 a,int64 b) {
    long double res = (long double) a * b / mod;
    int64 tmp = a * b, t1 = (tmp - (uint64)res * mod + mod) % mod;
    return t1;
}

本质上就是通过 $l o n g d o u b l e$ 的性质。

这里有个细节就是如果 $m o d^{2}$ 的话 $6$ 的逆元需要用 $e x g c d$ 来求。

cpp

#include <bits/stdc++.h>
using namespace std;
namespace Legendgod {
    namespace Read {
//        #define Fread
        #ifdef Fread
        const int Siz = (1 << 21) + 5;
        char *iS, *iT, buf[Siz];
        #define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
        #define getchar gc
        #endif
        template <typename T>
        void r1(T &x) {
            x = 0;
            char c(getchar());
            int f(1);
            for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
            for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
            x *= f;
        }
        template <typename T, typename...Args>
        void r1(T &x, Args&...arg) {
            r1(x), r1(arg...);
        }
        #undef getchar
    }

using namespace Read;

#define int long long
typedef long long int64;
typedef unsigned long long uint64;
const int maxn = 1e7 + 5;
const int64 mod0 = 1e9 + 7, mod1 = mod0 * mod0;
int64 mod = 1e9 + 7;

int64 n, m, A;

bitset<maxn> vis;
int pr[664579 + 5], tot(0), mu[maxn];

void init(int x) {
    vis.reset();
    mu[1] = 1;
    for(int i = 2; i <= x; ++ i) {
        if(!vis[i]) pr[++ tot] = i, mu[i] = - 1;
        for(int64 j = 1, k; k = 1ll * pr[j] * i, k <= x && j <= tot; ++ j) {
            vis[k] = 1;
            if(!(i % pr[j])) break;
            mu[k] = - mu[i];
        }
    }
    for(int i = 1; i <= x; ++ i) mu[i] += mu[i - 1];
}

int pd;

int64 Mul(int64 a,int64 b) {
    long double res = (long double) a * b / mod;
    int64 tmp = a * b, t1 = (tmp - (uint64)res * mod + mod) % mod;
    return t1;
}

int64 ksm(int64 x,int64 mi) {
    mi %= (mod - 1);
    int64 res(1);
    while(mi) {
        if(mi & 1) res = Mul(res, x);
        mi >>= 1;
        x = Mul(x, x);
    }
    return res;
}

void exgcd(int64 a, int64 b, int64 &x,int64 &y) {
    if(b == 0) return x = 1, y = 0, void();
    exgcd(b, a % b, x, y);
    int64 z = y; y = x - a / b * y, x = z;
}

int64 Inv(int64 c, int64 md) {
    int64 x, y;
    exgcd(c, mod, x, y);
    return x;
}

void Solvem() {
    m = 0;
    for(int64 i = 1, last; i <= A; i = last + 1) {
        last = min(A, A / (A / i));
        int64 tmp = A / last, tmp1 = mu[last] - mu[i - 1];
        m = (m + Mul(Mul(Mul(tmp, tmp), tmp), tmp1)) % mod;
        m = (m + Mul(3, Mul(Mul(tmp, tmp), tmp1))) % mod;
    }
    m = (m + 2) % mod;
    int64 iv = Inv(6, mod);
    m = Mul(m, iv);
//    printf("m = %lld\n", m);
    m = (m + mod) % mod;
}

int64 F(int64 n) {
    int64 tmp = ksm(m - 1, n) + (n & 1 ? -1 : 1) * (m - 1);
    tmp = (tmp + mod) % mod;
    return tmp;
}

int up[50], ps[50], ed;

void pre(int64 n) {
    ed = 0;
    for(int i = 1; i <= tot && pr[i] <= n; ++ i) if(n % pr[i] == 0) {
        up[++ ed] = pr[i], ps[ed] = 0;
        while(!(n % pr[i])) ++ ps[ed], n /= pr[i];
    }
    if(n != 1) up[++ ed] = n, ps[ed] = 1;
//    for(int i = 1; i <= ed; ++ i) {
//        printf("%d %d\n", up[i], ps[i]);
//    }
}

int64 ans(0);

void dfs(int dep, int64 d, int64 phi) {
    if(dep == ed + 1) {
        ans = (ans + Mul(phi, F(n / d))) % mod;
        return ;
    }
    dfs(dep + 1, d, phi);
    d *= up[dep], phi *= up[dep] - 1;
    dfs(dep + 1, d, phi);
    for(int i = 2; i <= ps[dep]; ++ i)
        d *= up[dep], phi *= up[dep], dfs(dep + 1, d, phi);
}

signed main() {
//    printf("%.3lf\n", fabs(&edd - &bg) / 1024.0 / 1024.0);
    int i, j, T;
    init(maxn - 5);
//    puts("SSS");
    r1(T);
    while(T --) {
        r1(n, A);
        if(n % mod0 == 0) mod = mod1, pd = 1;
        else mod = mod0, pd = 0;
        Solvem();
        pre(n);
        ans = 0;
        dfs(1, 1, 1);
        if(pd == 0) ans = Mul(ans, ksm(n, mod - 2));
        else ans = Mul(ans / mod0, ksm(n / mod0, mod0 - 2)) % mod0;
        ans = (ans + mod0) % mod0;
        printf("%lld\n", ans);
    }
    return 0;
}
/*
1
2000000014 4
*/
}

signed main() { return Legendgod::main(), 0; }