# 官方题解 | 第三届飞翔杯提高组

hopebetter

2025-06-14 17:38:50

发布于：浙江

215阅读

0回复

0点赞

T1

题解

记 $p^{-1}_{p_x} = x$ 。

直接模拟题意的时间复杂度是 $O(n^5)$ 。对求 $\mathrm{mex}$ 的方法稍加优化即可做到 $O(n^4)$ 。

对于特殊性质 A，立刻注意到 $\operatorname{mex} \lbrace p_1 \dots, p_k \rbrace = k + 1$ 当且仅当 $\forall i, p_i = i$
，故答案全 $0$ 。

下面先给出正解。

首先，注意到 $\operatorname{mex} \lbrace p_l, \dots, p_r \rbrace$ 不变，等价于 $(l \le x \le r) = (l \le y \le r)$
或 $\min \lbrace p_x, p_y \rbrace > \operatorname{mex} \lbrace p_l, \dots, p_r \rbrace$ 。充分性与必要性分别显然。

于是， $(x, y)$ 是稳定化子，当且仅当不存在一个子段 $\lbrace p_l, \dots, p_r \rbrace$
，使得 $(l \le x \le r) \ne (1 \le y \le r)$
且 $\operatorname{mex} \lbrace p_l, \dots, p_r \rbrace \ge \min \lbrace p_x, p_y \rbrace$
；换句话说，即 $\forall 1 \le l < r \le n \text{ s.t. } \left \lbrace 1, \dots, \min \left \lbrace p_x, p_y \right \rbrace - 1 \right \rbrace \subset \left \lbrace p_l, \dots, p_r \right \rbrace$
，都成立 $(1 \le x \le r) = (1 \le y \le r)$ 。

进而想到枚举 $v = \min \lbrace p_x, p_y \rbrace$
。记 $L_v = \min_{1 \le w \le v} p^{-1}_w$ ， $R_v = \max_{1 \le w \le v} p^{-1}_w$ 。由于上一段分析中 $l, r$
的任意性，可以发现 $\lbrace x, y \rbrace = \lbrace p^{-1}_v, p^{-1}_u \rbrace \pod{u > v}$
是稳定化子，当且仅当 $L_v < \min \lbrace p^{-1}_v, p^{-1}_u \rbrace < \max \lbrace p^{-1}_v, p^{-1}_u \rbrace < R_v$ 。

对应到最终的计数上，就是位置 $p^{-1}_v$ 单点加 $R_v - L_v + 1 - v$ ， $L_v, \dots, R_v$ 中所有 $p_i > v$ 的位置 $i$ 加 $1$
。至此本题应不再有任何困难，一个树状数组即可解决问题。

时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$ 。

部分与正解思路接近或能够进行一些有效转化的选手，应当可以立刻将时间复杂度优化到 $O(n^3)$ 或 $O(n^2)$ ，获得一些子任务的分数。

对于排列随机的情形，应当只有 $O(\log^2 n)$ 对本质不同的 $(L_v, R_v)$ 。如果选手的时间复杂度与 $\sum R_v - L_v$
有关，这一子任务可能有所帮助。

对于特殊性质 C, D，可以发现 $l \ne 1$ 的区间都是平凡的，只需考虑 $l = 1$ 的情形，可能部分选手会推出较弱的转化。

示例代码

# include <bits/stdc++.h>

namespace stabilizer {
    using namespace std;

    class fenwick {
        vector<int> t;
        void add(size_t x, int const d) { while (x < t.size()) t[x] += d, x += x & -x; }

    public:
        fenwick(size_t const n): t(n + 1) {
        }

        void add(size_t const l, size_t const r, int const d) { add(l + 1, +d), add(r + 2, -d); }

        int test(size_t x) const {
            ++x;
            int y(0);
            while (x) y += t[x], x &= x - 1;
            return y;
        }
    };
}

int main() {
    using namespace std;
    using stabilizer::fenwick;
    int n;
    cin >> n;
    vector<int> p(n);
    vector<int> q(n);
    for (int &p: p) cin >> p, --p;
    for (int i(0); i != n; ++i) q[p[i]] = i;
    stabilizer::fenwick bit(n);
    vector<int> c(n);
    for (int i(0), l(n), r(0); i != n; ++i) {
        c[q[i]] += bit.test(q[i]);
        l = min(l, q[i]), r = max(r, q[i]);
        if (l != q[i] && q[i] != r)
            c[q[i]] += r - l - i, bit.add(l, r, +1);
    }
    for (int i(0); i != n; ++i)
        i == n - 1 ? cout << c[i] << endl : cout << c[i] << ' ';
}

T2

题解

$k = 1$ 时，显然：若 $n = 1$ 则存在唯一的珍贵片段；否则不存在珍贵片段。

$k = 2$ 时，分析顺序对可知：只有 $\left \lbrace \left \lbrace s_1, s_2 \right \rbrace \mid s_2 - s_1 = 1 \right \rbrace$
有可能成为珍贵片段，而这些片段的确珍贵，构造是非常容易的。

$k \ge 3$
时，所有片段皆珍贵，构造性的思路见下。记 $S = \lbrace s_1, \dots, s_k \rbrace, T = \lbrace 1, \dots, n \rbrace \setminus S$
。注意到，对于 $S$ 中的位置，必须令其单调上升；对于其余位置，令其单调下降是不劣的。可以考虑：对于 $T$
中的位置，能否令其要么无顺序前驱，要么无顺序后继？这个问题的答案是肯定的，只需令 $a_{s_1}, \dots, a_{s_k}$
在值域上连续即可。于是构造呼之欲出：在 $s_2$ 前令 $T$ 中位置的取值尽可能大；在 $s_2$
后令其尽可能小即可。至此，我们对任意的 $S$ ，构造出了一个满足条件的 $A$ 。于是所有片段皆珍贵。

故答案为 $\begin{cases} [n = 1] & k = 1 \\ n - 1 & k = 2 \\ \binom n k & k = 3 \\ \end{cases}$ 。

直接计算的时间复杂度可以轻松做到 $O(k^2)$ ，优化为 $O(k)$
的技巧无非应用 $\binom n k = \frac {n - k + 1} k \binom n {k - 1}$ 。

示例代码

# include <bits/stdc++.h>

int main() {
  using namespace std;

  constexpr int64_t P(998244353);
  int64_t t;
  cin >> t;
  for (int64_t _(1); _ <= t; ++_) {
    int64_t n, m;
    cin >> n >> m;
    static vector<int64_t> inv(1);
    inv.reserve(m + 1);
    while (inv.size() <= size_t(m)) {
      int64_t const x(inv.size());
      inv.push_back(x == 1 ? 1 : inv[P % x] * (P - P / x) % P);
    }
    auto const binom = [] (int64_t const n, int64_t const m) {
      int64_t res(1);
      for (int64_t i(1); i <= m; ++i) res = res * (n - i + 1) % P;
      for (int64_t i(1); i <= m; ++i) res = res * inv[i] % P;
      return res;
    };
    vector<int64_t> ans(m + 1);
    for (int64_t k(1); k <= m; ++k)
      switch (k) {
        case 1 : ans[k] = n == 1; break;
        case 2 : ans[k] =  (n - 1)%P; break;
        case 3 : ans[k] = binom(n, k); break;
        default: ans[k] = (n - k + 1) * inv[k] % P * ans[k - 1] % P; break;
      }
    
    cout << accumulate(ans.begin(), ans.end(), 0ll, bit_xor<int64_t>()) << endl;
  }
}

T3

题解

首先进一步压缩使得 $\forall i, b_i \ne b_{i + 1}$ 。

先考察回文子串的形式。

对于一个子串 $s_l \dots s_r$ ，考察其跨过的压缩信息数 $k$ 。

首先注意到 $2 \mid k$ 的子串不可能回文。

$k = 1$ 的子串自然回文。

对于 $k \ge 3$ 的子串，可以发现除头尾外的 $k - 2$ 个压缩信息必定构成压缩信息意义上的长度为 $k - 2$ 的回文串。所以，直接对压缩信息运行
Manacher 算法或哈希后二分，求出以每个位置为中心的最长回文半径，同时对 $\lbrace a_1, \dots, a_n \rbrace$
做前缀和，即可简单勾勒出以每条信息为中心的 $k \ge 3$ 的回文子串之样貌。

于是，回文串被自然地分成了两类。

对于第一类，设该压缩信息为 $s_{p + 1} \dots s_{n - q} = c^o$ ，则对答案的贡献为

$\begin{aligned} & \sum_{l = 1}^m \sum_{r = 1}^m \sum_{x = 1}^o \sum_{y = 1}^o [l \le p + x \le (n - q + 1) - y \le r] \\ = & \sum_{x = 1}^o \sum_{y = 1}^{o - l + 1} (p + x) (q + y) \\ = & \sum_{x = 1}^o \sum_{y = 1}^{o - l + 1} (pq + px + qy + xy) \\ = & \left(\sum_{x = 1}^o \sum_{y = 1}^{o - l + 1} 1 \right) pq + \left(\sum_{t = 1}^o t (o - t + 1) \right)(p + q) + \left( \sum_{x = 1}^o \sum_{y = 1}^{o - l + 1} xy \right) \\ = & \binom {o + 1} 2 pq + \left( (o + 1) \binom {o + 1} 2 - \sum_{t = 1}^o t^2 \right) (p + q) + \binom {o + 3} 4 \\ \end{aligned}$

而 $\sum_{k = 1}^n k^2 = \frac{n (n + 1) (2n + 1)} 6$ 是经典的，于是上式可 $O(1)$ 计算。

对于第二类，同理上类，贡献无非以下形式：

$\begin{aligned} & \sum_{t = 0}^{k - 1} (l - t) (r - t) \\ = & klr - \binom k 2 (l + r) + \sum_{t = 0}^{k - 1} t^2 \\ \end{aligned}$

亦可 $O(1)$ 计算。

若使用 Manacher 算法，总时空复杂度皆为 $O(n)$ 。

示例代码

# include <bits/stdc++.h>

int main() {
    using namespace std;
    long long sum_len = 0;
    int64_t P(998244353);
      auto inv = [&](__int128 x) {
        x = (x % P + P) % P, assert(0 < x && x < P);
        __int128 y(1);
        while (x != 1) y = y * -(P / x) % P, x = P % x;
        return (y + P) % P;
    };
    __int128 inv2(inv(2));
    __int128 inv6(inv(6));
    __int128 inv24(inv(24));
      auto e2
            = [&](__int128 const n) { return n * (n + 1) / 2; };
      auto e4
            = [&](__int128 const n) { return n * (n + 1) % P * (n + 2) % P * (n + 3) % P * inv24 % P; };
      auto p2
            = [&](__int128 const n) { return n * (n + 1) % P * (2 * n + 1) % P * inv6 % P; };
     auto s2
            = [&](int64_t const n) { return (e2(n) * (n + 1) - p2(n)) % P; };
    int64_t n;
    cin >> n;
    vector<pair<__int128, char> > s;
    for (__int128 i(0); i != n; ++i) {
        int64_t a;
        char b;
      
        cin >> a >> b;
          sum_len += a;
        if (s.empty() || b != s.back().second) s.emplace_back(0, b);
        s.back().first += a;
    }
    vector<__int128> r(n = s.size());
    for (__int128 i(0), j(0); i != n; ++i) {
        if (i <= j + r[j]) r[i] = min(r[2 * j - i], j + r[j] - i);
        while (0 < i - r[i] && i + r[i] + 1 < n)
            if (s[i - r[i] - 1] == s[i + r[i] + 1]) ++r[i];
            else break;
        if (i + r[i] > j + r[j]) ++j;
    }
    vector<__int128> t(n + 1);
    for (__int128 i(0); i != n; ++i)
        t[i + 1] = t[i] + s[i].first;
    int64_t ans(0);
    for (__int128 i(0); i != n; ++i) {
        __int128   o(s[i].first);
        __int128   u(t[i]);
        __int128   v(t[n] - t[i + 1]);
        o%=P,u%=P , v%=P;
        ans = (ans + (u * v) % P * e2(o)) % P;
        ans = (ans + (u + v) % P * s2(o)) % P;
        ans = (ans + e4(o)) % P;
    };
    for (__int128 i(0); i != n; ++i) {
        __int128 len(t[i] - t[i - r[i]]);
        if (0 < i - r[i] && i + r[i] + 1 < n)
            if (s[i - r[i] - 1].second == s[i + r[i] + 1].second)
                len += min(s[i - r[i] - 1].first, s[i + r[i] + 1].first);

        __int128   u(t[i]), v(sum_len - t[i + 1]);;
        len %= P;
        u%=P , v%=P;
        ans = (ans + (u * v) % P * len) % P;
        ans = (ans - (u + v) % P * e2(len - 1)) % P;
        ans = (ans + p2(len - 1)) % P;
    }
    cout << (ans + P) % P << endl;
}

T4

题解

记 $C = \max \lbrace a_i, b_j \rbrace$ 。记全体质数构成的集合为 $\mathbb P$ 。

正解之思路是直接的：

$\begin{aligned} & \sum_{t \in A} f(s, t) \\ = & \sum_{t \in A} \frac t {\gcd(s, t)} \\ = & \sum_{x \mid s} \frac 1 x \sum_{x \mid t \in A} t \left[ \gcd(s, t) = x \right] \\ = & \sum_{x \mid s} \frac 1 x \sum_{x \mid t \in A} t \sum_{xy \mid \gcd(s, t)} \mu(y) \\ = & \sum_{xy \mid s} \frac {\mu(y)} x \sum_{xy \mid t \in A} t \\ = & \sum_{m \mid s} \left( \sum_{y \mid m} \frac {y \mu(y)} m \right) \left( \sum_{m \mid t \in A} t \right) \\ = & \sum_{m \mid s} \left( \sum_{y \mid m} y \mu(y) \right) \left( \frac 1 m \sum_{m \mid t \in A} t \right) \\ \triangleq & \sum_{m \mid s} f(m) \frac {g(m)} m \\ \end{aligned}$

其中， $\mu(\cdot)$ 可以线性筛出； $f(\cdot), g(\cdot)$ 及最后一个 $\sum$ 均为 Dirichlet
前缀和或后缀和的形式，可以 $O(C \log \log C)$ 时间 $O(C)$ 空间求出。

于是，在 $O(C \log \log C)$ 时间 $O(C)$ 空间的预处理后，可以单次 $O(1)$ 地回答询问。总时间复杂度 $O(n + C \log \log C)$
，总空间复杂度 $O(C)$ 。

下就部分子任务给出简要思路。

对于测试点 $1, 2$ ，直接或在对 $A$ 中 $1, \dots, C$ 计数后，模拟题意即可。

对于特殊性质 A, C，注意到以下事实后，对每个质数 $p$ 记录 $\sum [p \mid a_i]$ 与 $\sum a_i [p \mid a_i]$ ，进而求出答案并无任何困难。

$f(x, y) = \begin{cases} y & x \perp y & \pod 1 \\ 1 & y \mid x & \pod 2 \\ \frac y x & x \mid y & \pod 3 \\ r & x = pq, y = qr, (p, q, r \in \mathbb P), p \ne r & \pod 4 \\ \end{cases}$

对于特殊性质 B1，其思路与正解几乎全同，无非在推导过程中将一些 $\sum_{t \in A}$ 改为 $\sum_{t = 1}^n$ 而已。

示例代码

# include <bits/stdc++.h>

int main() {
    using namespace std;

    int n;
    cin >> n;
    vector<int> a(n);
    for (int &a: a) cin >> a;
    int m;
    cin >> m;
    vector<int> b(m);
    for (int &b: b) cin >> b;
    int const A(*max_element(a.begin(), a.end()));
    int const B(*max_element(b.begin(), b.end()));
    int const C(max(A, B));
    vector<int> isprime(C + 1, true);
    vector<int> prime, mu(C + 1);
    isprime[1] = isprime[0] = false, mu[1] = 1;
    for (int i(2); i <= C; ++i) {
        if (isprime[i]) {
            prime.push_back(i);
            mu[i] = -1;
        }
        for (int const j: prime) {
            if (i * j > C) break;
            isprime[i * j] = false;
            if (i % j) mu[i * j] = -mu[i];
            else break;
        }
    }
    vector<int64_t> f(C + 1);
    vector<int64_t> g(C + 1);
    vector<int64_t> h(C + 1);
    for (int i(1); i <= C; ++i) f[i] = i * mu[i];
    for (int const p: prime)
        for (int i(1); p * i <= C; ++i) f[p * i] += f[i];
    for (int const a: a) g[a] += a;
    for (int const p: prime)
        for (int i(C / p); i >= 1; --i) g[i] += g[p * i];
    for (int i(1); i <= C; ++i) h[i] = g[i] / i * f[i];
    for (int const p: prime)
        for (int i(1); p * i <= C; ++i) h[p * i] += h[i];
    for (int const b: b) cout << h[b] << endl;
}

有帮助，赞一个

去预览

0/2000

全部评论 10

Gragher
老师的码风也是风韵犹存（vector

2025-06-14 来自浙江
1
- Gragher
  回复Gragher
  是极为少见的动态数组派
  
  2025-06-14 来自浙江
  0
- tourist
  回复Gragher
  9494
  
  2025-06-15 来自广东
  0
tourist
666

2025-06-14 来自广东
1
sigma
现在的 T3 std 还是挂的，我正确的代码只有 44 分。

2025-06-14 来自北京
1
- ༺ཌༀ老师好我叫涂同学ༀད༻
  回复sigma
  zc
  
  2025-06-14 来自浙江
  0
- Gragher
  回复sigma
  啊，你怎么确定自己的事正确代码（？）（xxs，喷轻点
  
  2025-06-14 来自浙江
  0
- Gragher
  回复Gragher
  事->是
  
  2025-06-14 来自浙江
  0
cjdstttttt
赛时 T1 只拿了 60pts，结果现在发现加个懒标记就能 A 的

2025-07-27 来自湖南
0
- cjdstttttt
  回复cjdstttttt
  额滴算法竞赛啊啊啊啊啊啊啊
  
  2025-07-27 来自湖南
  0
复仇者-小青蛙a号
广告

2025-06-16 来自北京
0
ask_silently
T1 似乎有 O(n) 做法

2025-06-16 来自河南
0
sigma
好吧，已经修改了数据，也就是说，2h 能 AK 的比赛硬是拖了我 1h 来给 std 查错。

2025-06-16 来自北京
0
AAA水泥批發白哥
%%%

2025-06-15 来自北京
0
‮++c吧蛋滚
啊……

2025-06-14 来自浙江
0
???
沙发

2025-06-14 来自广东
0

T1

题解

示例代码

T2

题解

示例代码

T3

题解

示例代码

T4

题解

示例代码

全部评论 10

热门讨论