Polya 定理

胎教级入门篇

还是没有详细的证明。。

Burnside 定理

(烧边定理(?大雾))

对于一个置换 ff,我们定义 C(f)C(f) 为 在合成 ff 后保持相对于原来不变的方案数量,这里称作 不动点。不动点并不是一个点,而是一个方案

以染色为例,“不动点”即指染色方案,满足合成 ff 后染色不变。

那么本质不同的方案数量就是对于左右可用置换不动点个数平均值,形式化地写:

ans=1GfGC(f)ans = \frac 1 {|G|} \sum_{f \in G} C(f)

其中 GG 是一个置换群。

Polya 定理

我们考虑知道了 Burnside 定理后如何求染色方案数量。

对于一个置换 ff 我们可以设 L(f)L(f) 表示在 ifii \to f_i 连边后的环的数量,那么不难发现一个置换是不动点,等价于所有的环内的位置是等价的。

也就是说,我们可以略微改写 Burside 定理

ans=1GfGmL(f)ans = \frac 1 {|G|} \sum_{f\in G} m^{L(f)}

其中 mm 为每个位置的方案数量,有时候 mm 也可以替换为其他东西,反正就是每个环必须全部等价就完事了。

这就是 Polya 定理辣。

模版题

考虑 “旋转” 这个操作,不难发现所有可能的置换构成了一个置换群(也就是不旋转(单位元),旋转一次,两次,...,旋转 n1n-1 次)

我们可以直接枚举置换,也就是枚举旋转多少次,考虑旋转 kk 次时不动点的个数,也就是旋转 kk 次后的环的个数。

旋转 kk 次环的个数?这个东西前段时间我才被坑过(因为不知道这个结论 cf 某题爆炸),是 gcd(n,k)\gcd(n,k) ,所以答案是

1nk=1nngcd(k,n)\frac 1 n \sum_{k=1}^n n^{\gcd(k,n)}

然后老套路题了

=k=1nngcd(k,n)=k=1ni=1n[gcd(k,n)=i]ni=i=1nnik=1n[gcd(k,n)=i]=inniφ(ni)\begin{aligned}&= \sum_{k=1}^n n^{\gcd(k,n)}\\&= \sum_{k=1}^n \sum_{i=1}^n [\gcd(k,n) = i]n^{i}\\&= \sum_{i=1}^n n^i \sum_{k=1}^n[\gcd(k,n) = i]\\&= \sum_{i|n} n^i \varphi(\frac{n}{i})\end{aligned}

直接做就好了,求 φ\varphiO(n)O(\sqrt n) ,这个东西套用经典的复杂度分析是 O(n34)O(n^{\frac 3 4}) ,如果预处理一下前 n23n^\frac 2 3O(Tn23)O(Tn^\frac 2 3)

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 3000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 1000000007
typedef long long ll;
int n;

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = 1ll * ret * x % P;
        x = 1ll * x * x % P , a >>= 1;
    }
    return ret;
}

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

void solve() {
    scanf("%d",&n);
    int res = 0;
    for( int i = 1 ; i * i <= n ; ++ i ) if( n % i == 0 ) {
        ( res += 1ll * Pow( n , i ) * phi( n / i ) % P ) %= P;
        if( i * i != n ) ( res += 1ll * Pow( n , n / i ) * phi( i ) % P ) %= P;
    }
    printf("%d\n",1ll * res * Pow( n , P - 2 ) % P);
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
    int T;cin >> T;while( T-- ) solve();
//    solve();
}
\