DDOSvoid's Blog

2022杭电多校6 K Find different

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7207

简要题意：给定 $n$ 和 $m$，求有多少本质不同的序列 $a_i$，满足 $0\le a_i<m$，且 $a_i$ 可以重复循环左移任意次以及整体重复加任意次，对于 $k\in[1,n]$ 计算答案

$n,m\le 10^5$

Solution

注意到本质不同等价于求有多少长度为 $n$，每一位的大小为 $[0,m-1]$ 且和模 $m$ 为 $0$ 的圆环，我们首先不考虑最后一个条件，那么这显然是一个 $burnside$ 定理的题目，我们有 $n$ 个置换 $f$，第 $k$ 个置换满足 $p_i=i+k$，且第 $k$ 个置换有 $(n,k)$ 个循环，每个循环的大小都是 $\frac{n}{(n,k)}$，同时数字大小为 $[0,m-1]$ 相当于有 $m$ 种颜色，那么我们可以得到对于长度为 $n$ 的环，答案为 $\sum_{i=1}^n m^{(n,i)}$

我们现在考虑和模 $m$ 为 $0$ 这个条件，我们不妨设环大小为 $d$，环个数为 $\frac{n}{d}$，第 $i$ 个环的颜色为 $a_i$，那么我们必须有 $d\sum_{i=1}^{\frac{n}{d}}a_i\equiv 0(\bmod m)$，这个东西等价于 $\sum_{i=1}^{\frac{n}{d}}a_i\equiv 0(\bmod \frac{m}{(m,d)})$，我们知道 $a_i$ 在 $[0,m-1]$ 内均匀取值，那么 $\sum a_i\equiv k(\bmod m)$，其中 $k\in[0,m-1]$，的方案数是相同的，所以这个东西占总数的比列就是 $\frac{(m,d)}{m}$，那么原式就是 $\sum_{i=1}^nm^{(n,i)}\frac{(m,\frac{n}{(n,i)})}{m}$，这个东西我们化简一下可以得到 $\frac{1}{nm}\sum_{d|n}m^{d}\varphi(\frac{n}{d})(m,\frac{n}{d})$

时间复杂度 $O(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
55
56
57
58
59
60
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define maxn 100010
#define maxm 200010
#define INF 1000000000
#define ll long long
using namespace std;

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

const int p = 998244353;
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], cnt, phi[maxn]; bool isp[maxn]; vector<int> A[maxn];
void init_isp(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            } phi[i * pri[j]] = phi[i] * (pri[j] - 1); 
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) A[j].push_back(i);
}

int n, m, f[maxn];
ll ppow[maxn];

void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) f[i] = gcd(i, m);
    ppow[0] = 1; for (int i = 1; i <= n; ++i) ppow[i] = ppow[i - 1] * m % p;
    for (int n = 1; n <= ::n; ++n) {
        ll ans = 0;
        for (auto d : A[n])
            ans = (ans + ppow[d] * f[n / d] % p * phi[n / d] % p) % p;
        cout << ans * pow_mod(1ll * n * m % p, p - 2) % p << " \n"[n == ::n];
    }
}

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

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