CF2176F Omega Numbers 题解

我不会啊。

感觉是若干套路的集合。

首先显然有 。对于 的情况下，可以计算所有 的值，用莫反或者子集反演计算 的值。

这里提一下用子集反演替代一部分莫反的情况。当你要求的函数只和质数集合 有关的时候，那么可以使用子集反演代替莫反。核心原理是在 的情况下，一个数不同质数的个数不会超过 个，稍后我们来讲解一下如何用这个解决这个题目。

但这个题目由于有 次幂的影响，我们很难将 暴力展开计算。因此我们必须要考虑枚举一些别的东西。

一个简单的想法是直接枚举 。做法是在对于每个数在其倍数的位置都 ，对于每个位置 假设最终有 个 ，计算 表示 最多是 的情况，然后做一个莫反。但是值域太大，很难做。

我们发现之所以想知道 是因为这个很方便算答案。我们继续观察，发现答案的范围也不大，最多 个，实际可能更少，因为质数会越来越大。

我们不妨直接枚举答案。我们分成两部分来计算， 和 。我们希望求出来 表示答案为 的对数。首先对于 ，这部分是好求的。质因数分解直接求即可。

接下来我们希望通过某些方法计算出 的方案数。这个乍一看可能很困难，但是处理这种东西有个套路。

后面部分可能需要你对偏序集合上的莫比乌斯反演有一定的了解。

对于一个集合 和 上的偏序关系 ， 被称作下半格当且仅当对于任意 ，集合 都有最大元。这个集合称作 的公共下界，最大元称作 的最大下界。

对于一个下半格，有如下性质。假设你在对于 满足 ，给 加上了 ，对 计算 的时候， 对 做的贡献就是 。

此时，如果 中有最大元 ，那么 对 做的贡献就是 。

下面是两个具体的例子。

  • 对于正整数 上的整除关系 ， 构成了一个下半格。 的最大下界即为 。
  • 对于一个集合的所有子集族 和集合的包含关系 ， 构成一个下半格。 的最大下界即为 。

你会发现， 对 做的贡献就是 是一个关于最大下界 的函数 。并且，我们可以任意定制这个函数 ，并且使用一次偏序集合的莫比乌斯反演算出来对应的 ，从而实现对 贡献任意关于 的函数。

举个例子，假设一个子集 ，你希望对任意的 ，假设 ，那么你希望 对 的贡献是 。此时你知道了若干个 之类的限制，你可以使用一次子集反演求出来这个 。此时你可以用一个数组 记录所有贡献，然后在所有 的位置，给 加上 。

此时你又拿到了另外一个集合 ，在需要计算贡献的时候，只需要计算 ，此时 对 的贡献就是 了。

同时，这也是莫比乌斯反演处理 的常见方式。

在本题中，我们拆成 个数组 ，依次表示 的贡献。

假设我们希望对所有 做出 的贡献，记录到 中。我们发现 函数只关心构成某个数的质数有哪些（只关心集合，实际上是集合大小）而不在意每个质数有几个，此时我们可以使用子集反演替换莫比乌斯反演。假设 的质数集合是 ， 的质数集合是 ，我们实际上要对 的情况作出 的贡献，移项发现 。此时的贡献函数是 ，其中的中括号表示艾弗森括号。对于每个子集 处理出 做一次子集反演得到 ，在 的位置加上 即可。对于每个 都做一遍即可。

计算贡献的时候，对于每个 ， 即为 的对数。此时直接统计答案即可。

可以通过选取 作为 的哈希函数来作为 对应的数组下标。由于 是质数，因此哈希值唯一，用一个值域大小的数组来存放即可。

然而我们发现对于每个数都做子集反演不现实，计算量高达 。对于一个大小为 的集合 的每个子集 有 ，我们可以预处理出它的 ，这样在加的时候只需要查表即可，不需要重新子集反演。

这样的复杂度就可以接受了。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include <array>
#include <iostream>
#include <vector>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

namespace maths {
template <ull mod, class int_type = ll, class uint_type = ull>
class modular {
  private:
    uint_type x;
    void norm() { x -= mod * (x >= mod); }

  public:
    modular() : x(0) {}
    modular(int_type _x) {
        if (_x < 0) {
            x = _x % (int_type)mod + (int_type)mod;
        }
        else {
            x = _x % mod;
        }
        norm();
        return;
    }
    friend modular operator+(const modular &lhs, const modular &rhs) {
        modular ret;
        ret.x = lhs.x + rhs.x;
        ret.norm();
        return ret;
    }
    friend modular operator-(const modular &lhs, const modular &rhs) {
        modular ret;
        ret.x = lhs.x + mod - rhs.x;
        ret.norm();
        return ret;
    }
    friend modular operator*(const modular &lhs, const modular &rhs) {
        return modular(lhs.x * rhs.x);
    }
    modular operator-() const {
        modular ret;
        ret.x = mod - x;
        return ret;
    }
    modular operator-=(const modular &b) { return *this = *this - b; }
    modular operator+=(const modular &b) { return *this = *this + b; }
    modular operator*=(const modular &b) { return *this = *this * b; }
    bool operator==(const modular &b) const { return x == b.x; }
    uint_type val() const { return x; }
    friend std::istream &operator>>(std::istream &is, modular &rhs) {
        is >> rhs.x;
        rhs.x %= mod;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const modular &rhs) {
        os << rhs.val();
        return os;
    }
};

using modint998244353 = modular<998244353>;
using modint1000000007 = modular<1000000007>;
} // namespace maths

namespace maths {
template <class T>
T quick_pow(T a, ull b, T id = T()) {
    T ret = id;
    for (; b; b >>= 1, a = a * a) {
        if (b & 1) {
            ret = a * ret;
        }
    }
    return ret;
}

template <class T>
T quick_pow(T a, const std::string &s, T id = T()) {
    T ret = id;
    for (size_t i = 0; i < s.size(); i++, a = a * a) {
        if (s[i] == '1') {
            ret = a * ret;
        }
    }
    return ret;
}

} // namespace maths

namespace solve {
const uint N = 8;

using mll = maths::modint998244353;

std::array<std::array<std::array<mll, 1u << N>, N>, N> val;

void prework() {
    for (size_t sz = 0; sz < N; sz++) {
        for (size_t i = 0; i <= sz; i++) {
            for (size_t j = 0; j < 1u << sz; j++) {
                val[sz][i][j] = (i == __builtin_popcountll(j));
            }

            for (size_t k = 0; k < sz; k++) {
                for (size_t j = 0; j < 1u << sz; j++) {
                    if ((j >> k) & 1) {
                        val[sz][i][j] -= val[sz][i][j ^ (1u << k)];
                    }
                }
            }
        }
    }
}

std::vector<uint> fact(uint x) {
    std::vector<uint> p;
    for (size_t i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            p.push_back(i);
            while (x % i == 0) {
                x /= i;
            }
        }
    }

    if (x > 1) {
        p.push_back(x);
    }

    return p;
}

void solve() {
    uint n, power;
    std::cin >> n >> power;
    std::vector<uint> a(n);
    for (size_t i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<std::array<mll, N>> cnt(n + 1);

    mll final_ans = 0;

    for (size_t i = 0; i < n; i++) {
        auto p = fact(a[i]);

        std::vector<uint> prod(1u << p.size());

        for (size_t stat = 0; stat < 1u << p.size(); stat++) {
            uint k = 1;
            for (size_t j = 0; j < p.size(); j++) {
                if ((stat >> j) & 1) {
                    k *= p[j];
                }
            }
            prod[stat] = k;
        }

        std::array<mll, N> total_cnt;

        for (size_t stat = 0; stat < 1u << p.size(); stat++) {
            for (size_t j = 0; j < N; j++) {
                total_cnt[j] += cnt[prod[stat]][j];
            }
        }

        for (size_t j = 0; j < N; j++) {
            uint real_ans = j + p.size();
            final_ans +=
                maths::quick_pow<mll>(real_ans, power, 1) * total_cnt[j];
        }

        for (size_t j = 0; j <= p.size(); j++) {
            uint subset_size = p.size() - j;

            for (size_t stat = 0; stat < 1u << p.size(); stat++) {
                cnt[prod[stat]][j] += val[p.size()][subset_size][stat];
            }
        }
    }

    std::cout << final_ans << "\n";
}
} // namespace solve

int main() {
    solve::prework();
    uint t;
    std::cin >> t;
    while (t--) {
        solve::solve();
    }
    std::cout << std::flush;
>}
OI > 题解
CF2176F Omega Numbers 题解
https://blogs.sving1024.top/posts/58554/
发布于
2026年7月14日
许可协议