DDOSvoid's Blog

Luogu P4980 【模板】Pólya 定理

发表于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P4980

Solution

首先能够得到我们的所有置换为 $f(k)=\dbinom {1,2,\cdots,n-k,n-k+1,\dots,n} {1+k,2+k,\cdots,n,1,\cdots,k}$

我们考虑 $f(k)$ 的作用下不变方案，首先从序列开始入手， 首先序列肯定有一个循环节 $t$，$t|n$ 且 $t|k$，那么 $t$ 就是 $(n,k)$

那么答案就是 $\frac 1 n \sum_{i=1}^n n^{(n,i)}$

简单化简可以得到 $\frac n 1 \sum_{d|n} n^{\frac n d}\varphi(d)$

这个东西可以通过先对 $n$ 分解质因数，然后 $dfs$ 所有约数的情况下顺便处理 $\varphi$ 做到 $O(T(\sqrt n+\sigma_0(n)\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
#define maxn 5010
#define ll long long
#define INF 1000000000
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
} 

int pri[maxn], num[maxn], cnt;
void decomposition(int n) {
    for (int p = 2; p * p <= n; ++p) {
        if (n % p) continue ;
        pri[++cnt] = p; num[cnt] = 0; 
        while (n % p == 0) ++num[cnt], n /= p; 
    }
    if (n > 1) pri[++cnt] = n, num[cnt] = 1; 
}

int n;

ll ans;
void dfs(int o, int d, int phi) {
    if (o == cnt + 1) return ans = (ans + pow_mod(n, n / d - 1) * phi) % p, void();
    for (int i = 0; i <= num[o]; ++i) {
        dfs(o + 1, d, phi);
        d *= pri[o];
        if (!i) phi *= pri[o] - 1;
        else phi *= pri[o];
    }
}

void work() {
    cin >> n; ans = cnt = 0;
    decomposition(n); dfs(1, 1, 1);
    cout << ans << "\n"; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}