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

userId_undefined

hopebetter

2025-06-14 17:38:50

发布于：浙江

215阅读
0回复
0点赞

T1

题解

记 ppx−1=xp^{-1}_{p_x} = x。

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

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

下面先给出正解。

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

于是，(x,y)(x, y) 是稳定化子，当且仅当不存在一个子段 {pl,…,pr}\lbrace p_l, \dots, p_r \rbrace
，使得 (l≤x≤r)≠(1≤y≤r)(l \le x \le r) \ne (1 \le y \le r)
且 mex⁡{pl,…,pr}≥min⁡{px,py}\operatorname{mex} \lbrace p_l, \dots, p_r \rbrace \ge \min \lbrace p_x, p_y \rbrace
；换句话说，即 ∀1≤l<r≤n s.t. {1,…,min⁡{px,py}−1}⊂{pl,…,pr}\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≤x≤r)=(1≤y≤r)(1 \le x \le r) = (1 \le y \le r)。

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

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

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

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

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

对于特殊性质 C, D，可以发现 l≠1l \ne 1 的区间都是平凡的，只需考虑 l=1l = 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=1k = 1 时，显然：若 n=1n = 1 则存在唯一的珍贵片段；否则不存在珍贵片段。

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

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

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

直接计算的时间复杂度可以轻松做到 O(k2)O(k^2)，优化为 O(k)O(k)
的技巧无非应用 (nk)=n−k+1k(nk−1)\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

题解

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

先考察回文子串的形式。

对于一个子串 sl…srs_l \dots s_r，考察其跨过的压缩信息数 kk。

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

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

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

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

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

∑l=1m∑r=1m∑x=1o∑y=1o[l≤p+x≤(n−q+1)−y≤r]=∑x=1o∑y=1o−l+1(p+x)(q+y)=∑x=1o∑y=1o−l+1(pq+px+qy+xy)=(∑x=1o∑y=1o−l+11)pq+(∑t=1ot(o−t+1))(p+q)+(∑x=1o∑y=1o−l+1xy)=(o+12)pq+((o+1)(o+12)−∑t=1ot2)(p+q)+(o+34)\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}

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

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

∑t=0k−1(l−t)(r−t)=klr−(k2)(l+r)+∑t=0k−1t2\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)O(1) 计算。

若使用 Manacher 算法，总时空复杂度皆为 O(n)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⁡{ai,bj}C = \max \lbrace a_i, b_j \rbrace。记全体质数构成的集合为 P\mathbb P。

正解之思路是直接的：

∑t∈Af(s,t)=∑t∈Atgcd⁡(s,t)=∑x∣s1x∑x∣t∈At[gcd⁡(s,t)=x]=∑x∣s1x∑x∣t∈At∑xy∣gcd⁡(s,t)μ(y)=∑xy∣sμ(y)x∑xy∣t∈At=∑m∣s(∑y∣myμ(y)m)(∑m∣t∈At)=∑m∣s(∑y∣myμ(y))(1m∑m∣t∈At)≜∑m∣sf(m)g(m)m\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(⋅),g(⋅)f(\cdot), g(\cdot) 及最后一个 ∑\sum 均为 Dirichlet
前缀和或后缀和的形式，可以 O(Clog⁡log⁡C)O(C \log \log C) 时间 O(C)O(C) 空间求出。

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

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

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

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

f(x,y)={yx⊥y(1)1y∣x(2)yxx∣y(3)rx=pq,y=qr,(p,q,r∈P),p≠r(4)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，其思路与正解几乎全同，无非在推导过程中将一些 ∑t∈A\sum_{t \in A} 改为 ∑t=1n\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;
}
userId_undefined
去预览
0/2000

全部评论 10

热门讨论