Chlience

【题解】LUOGU 4980 【模板】Polya定理
Problem给定 $n$ 个点的环,用 $m$ 种颜色进行染色,问有多少种本质不同的方案仅考虑旋转同构Thoug...
扫描右侧二维码阅读全文
13
2019/01

【题解】LUOGU 4980 【模板】Polya定理

Problem

给定 $n$ 个点的环,用 $m$ 种颜色进行染色,问有多少种本质不同的方案
仅考虑旋转同构

Thought

既然只考虑旋转同构,那么利用 $Polya$ 原理就能很简单的做出来

$$ L=\frac{1}{|G|}\sum_{i=1}^sm^{c(g_i)} $$

显然,$c(g_i)=gcd(i,n)$

那么就是求:

$$ \frac{1}{|G|}\sum_{i=1}^sm^{gcd(i,s)} $$

如果朴素的去做,时间复杂度为 $O(n\log n)$,显然是不可以接受的

因为 $gcd(i,n)$ 显然是 $\sqrt n$ 级别的,所以可以考虑枚举 $gcd(i,n)$
那么对于每个枚举的 $p$,共有 $\sum_{i=1}^n[gcd(i,n)=p]$ 个满足的元素

进一步变形得:

$$ \sum_{i=1}^{\frac{n}{p}}[gcd(i,\frac{n}{p})=1] $$

由 $\phi$ 的定义可得:

$$ \phi(\frac{n}{p})=\sum_{i=1}^{\frac{n}{p}}[gcd(i,\frac{n}{p})=1] $$

那么原式可以转化为

$$ \frac{1}{|G|}\sum_{p|n}\phi(\frac{n}{p})*m^{p} $$

总时间复杂度 $O(\sqrt n\log n)$

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int mod = 1000000007;
bool np[N];
int pri[N] , pri_num;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
void getPri() {
    for(int i = 2 ; i < N ; ++ i) {
        if(!np[i])
            pri[++ pri_num] = i;
        for(int j = 1 ; j <= pri_num && i * pri[j] < N ; ++ j) {
            np[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}
int getPhi(int x) {
    int phi = 1;
    for(int i = 1 ; i <= pri_num && pri[i] <= x ; ++ i) {
        if(x % pri[i] == 0) {
            phi *= (pri[i] - 1);
            x /= pri[i];
            while(x % pri[i] == 0) {
                phi *= pri[i];
                x /= pri[i];
            }
        }
    }
    if(x != 1)
        phi *= (x - 1);
    return phi;
}
int qpow(int a , int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    getPri();
    int t = read();
    while(t --) {
        int n = read() , ans = 0;
        for(int i = 1 ; i * i <= n ; ++ i)
            if(n % i == 0) {
                ans += 1ll * getPhi(n / i) * qpow(n , i) % mod;
                if(ans >= mod) ans -= mod;
                if(i * i != n) {
                    ans += 1ll * getPhi(i) * qpow(n , n / i) % mod;
                    if(ans >= mod) ans -= mod;
                }
            }
        printf("%lld\n" , 1ll * ans * qpow(n , mod - 2) % mod);
    }
    return 0;
}
Last modification:January 14th, 2019 at 07:27 am

Leave a Comment