P11835 [省选联考 2025] 封印 题解

Description

在一次探险中，小 H 发现了一个古老的封印。封印的本体是一个长度为 nn 的序列 A=[a1,a2,…,an]A = [a_1, a_2, \ldots, a_n]。初始，每个元素都是 11 至 mm 间的正整数。

设 ∣A∣|A| 表示序列 AA 的长度，小 H 可以对序列进行以下修改:

  1. 选择序列 AA 的某个严格前缀最大值元素 asa_s，即选择 1≤s≤∣A∣1 \leq s \leq |A| 满足 ∀1≤j<s,as>aj\forall 1 \leq j < s, a_s > a_j，特别地，a1a_1 总是序列 AA 的严格前缀最大值;
  2. 若 as≠1a_s \neq 1，将 (as−1)(a_s - 1) 插入序列 AA 的尾端;
  3. 删去序列 AA 的前 ss 个元素。

考虑如下例子：在 A=[1,3,2,3,4]A = [1, 3, 2, 3, 4] 时，

  • 小 H 可以选择 s=1s = 1，此时修改后的序列变为 [3,2,3,4][3, 2, 3, 4];
  • 小 H 可以选择 s=2s = 2，此时修改后的序列变为 [2,3,4,2][2, 3, 4, 2];
  • 小 H 不能选择 s=4s = 4，因为 a2=a4=3a_2 = a_4 = 3，这意味着 a4a_4 并非严格前缀最大值。

小 H 可以进行任意多次修改操作，也可以不进行任何修改。为了解开封印，小 H 想知道：通过以上修改操作，他可以得到多少种不同的非空序列。

认为两个序列 A=[a1,…,an]A = [a_1, \ldots, a_n] 和 B=[b1,…,bm]B = [b_1, \ldots, b_m] 不同，当且仅当 n≠mn \neq m 或 ∃1≤i≤min⁡{n,m}\exists 1 \leq i \leq \min\{n, m\}，ai≠bia_i\neq b_i

由于答案可能很大，你只需告诉小 H 答案对 998 244 353998\,244\,353 取模后的结果。

Solution

设操作次数最多的数的操作次数为轮数，容易发现不同轮之间的状态一定不会互相影响，因为最大值一定不相同。

注意到第二轮及以后的操作剩下的数一定可以在第一轮的时候截取出来，后面就变为每次必须选择开头操作的问题，所以考虑把第一轮和第二轮及以后的方案分开算。

首先是第二轮及以后的贡献。

先选择一个子集 SS 表示方案由 SS 中的数操作后构成，SS 需要满足 aSia_{S_i} 为 aSi−1+1a_{S_{i-1}+1} 到 aSia_{S_i} 的严格前缀最大值，且 aS1a_{S_1} 必须比 aS∣S∣a_{S_{|S|}} 之后的数加一还大。

可以证明只要满足这个条件，不同的集合 SS 算出的方案一定不重。

证明

显然 SS 一定包含全局最大值，那么如果存在两个集合 S1,S2S_1,S_2 存在某个循环序列重复了，可以根据最大值的个数和位置得知它们操作的总次数  mod ∣S1∣\bmod |S_1| 一定相等。

根据这个就可以得知两个集合每个位置的值一一相等，所以 S1S_1 和 S2S_2 每个位置也一定一一对应。

不妨设最小值的位置是 pp，则贡献为 (min⁡−2)⋅∣S∣+p(\min-2)\cdot |S|+p，而把最小值删掉后的贡献会被其它集合算到。

但是这样做有 corner case，在 2 1 1 这组数据下删掉任何数都是不合法的。

考虑什么样的情况不会被算到。

容易发现 p+1∼∣S∣p+1\sim |S| 一定都是最小值且第一个一定是最小值加一，否则把最右边的最小值删掉即可合法。

同时 1∼p−11\sim p-1 都是最小值加一，否则选择第一个不是最小值加一的删掉也能合法。

所以 corner case 一定形如 {min⁡+1,min⁡+1,…,min⁡,min⁡}\{\min+1,\min+1,\ldots,\min,\min\}，这部分有额外的 ∣S∣−1|S|-1 的贡献。

按照上面的做法可得到一个 O(2nn)O(2^nn) 的做法，优化就枚举第一个最小值然后 dp 即可。

然后是第一轮的贡献。

同样是对选出的子集计数，先给出做法：

  1. 选择第一个 11 之后就一直选 11。
  2. 不能第一个选 22 且最后一个选序列末尾的 11。

不满足上面两个条件一定是不合法的，因为一定存在一种方案能够选择更少的数且方案一样。

下面是满足这两个条件后不会算重的不严谨感性证明。

证明

设全局最大值为 mxmx。

同样是通过最大值定位，对于一种方案，如果里面存在 mxmx，则原序列上的最后一个 mxmx 一定对应方案内的最后一个 mxmx，所以可以根据此得到最后一个选的数的位置，也就唯一确定了一种选择。

如果不存在 mxmx，说明每个 mxmx 都被选了，那么把新序列上最后一个 mx−1mx-1 一定对应原序列上的最后一个 mxmx，也就能够得到原序列每个 mxmx 对应的位置。考虑把原序列第一个 mxmx 到最后一个 mxmx 之间的数全部删掉，方案里的第一个 mx−1mx-1 到最后一个 mx−1mx-1 也删掉后就归纳了一个规模更小的问题。

对这个直接 dp 即可做到 O(n2)O(n^2)。

时间复杂度：O(n2)O(n^2)。

Code

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
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 2.5e3 + 5, kMod = 998244353;

int cid, n, m;
int a[kMaxN];

int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

namespace Part1 {
int f[kMaxN][2][2];

int solve() {
  int ans = 1;
  for (int i = 1, mx = 0; i <= n; ++i) {
    memset(f[i], 0, sizeof(f[i]));
    if (a[i] > mx) {
      f[i][a[i] != 1][a[i] == 2] = 1;
    }
    for (int j = i - 1, mx = 0; j; --j) {
      if (a[i] > mx) {
        for (int o1 = 0; o1 < 2; ++o1) {
          for (int o2 = 0; o2 < 2; ++o2) {
            if (!(!o1 && a[i] > 1))
              inc(f[i][o1 & (a[i] > 1)][o2], f[j][o1][o2]);
          }
        }
      }
      mx = std::max(mx, a[j]);
    }
    mx = std::max(mx, a[i]);
    inc(ans, add(add(f[i][0][0], f[i][0][1]), add(f[i][1][0], f[i][1][1])));
  }
  if (m > 2 && a[n] == 1) dec(ans, add(f[n][0][1], f[n][1][1]));
  return ans;
}
} // namespace Part1

namespace Part2 {
int pre[kMaxN], fir[kMaxN];

void prework() {
  static int stk[kMaxN];
  int top = 0;
  for (int i = 1; i <= n; ++i) {
    for (; top && a[i] > a[stk[top]]; --top) {}
    pre[i] = stk[top], stk[++top] = i;
  }
}

int solve() {
  int len = n;
  n = 0;
  for (int i = 1; i <= len; ++i) {
    if (a[i] > 1) a[++n] = a[i];
  }
  if (!n) return 0;
  prework();
  for (int i = 1; i <= n; ++i) {
    fir[i] = 0;
    for (int j = n; j; --j) {
      if (a[i] <= a[j] + 1) {
        fir[i] = j; break;
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    static int f[kMaxN], cntf[kMaxN], g[kMaxN], cntg[kMaxN];
    static int df[kMaxN], dcntf[kMaxN], dg[kMaxN], dcntg[kMaxN];
    int val = a[i] - 2;
    for (int i = 0; i <= n; ++i) {
      f[i] = cntf[i] = g[i] = cntg[i] = 0;
      df[i] = dcntf[i] = dg[i] = dcntg[i] = 0;
    }
    f[i] = val, g[i] = 0, cntf[i] = cntg[i] = 1;
    int ff = 0, cntff = 0;
    for (int j = i; j; --j) {
      inc(ff, df[j]), inc(cntff, dcntf[j]);
      if (a[j] > a[i]) {
        f[j] = ff, cntf[j] = cntff;
      }
      inc(ff, add(f[j], 1ll * (val + 1) * cntf[j] % kMod));
      inc(cntff, cntf[j]);
      if (pre[j]) {
        dec(df[pre[j] - 1], add(f[j], 1ll * (val + 1) * cntf[j] % kMod));
        dec(dcntf[pre[j] - 1], cntf[j]);
      }
    }
    for (int j = i; j <= n; ++j) {
      if (j != i && a[j] >= a[i]) {
        g[j] = sub(dg[j - 1], dg[std::max(pre[j] - 1, 0)]);
        cntg[j] = sub(dcntg[j - 1], dcntg[std::max(pre[j] - 1, 0)]);
      }
      dg[j] = add(dg[j - 1], add(g[j], 1ll * val * cntg[j] % kMod));
      dcntg[j] = add(dcntg[j - 1], cntg[j]);
    }
    static int sg[kMaxN], scntg[kMaxN];
    for (int j = 1; j <= n; ++j) {
      sg[j] = add(sg[j - 1], g[j]);
      scntg[j] = add(scntg[j - 1], cntg[j]);
    }
    for (int j = 1, mx = 0; j <= i; ++j) {
      if (a[j] > mx) {
        inc(ans, 1ll * f[j] * sub(scntg[n], scntg[std::max(i, fir[j]) - 1]) % kMod);
        inc(ans, 1ll * cntf[j] * sub(sg[n], sg[std::max(i, fir[j]) - 1]) % kMod);
      }
      mx = std::max(mx, a[j]);
    }
  }
  --ans;
  for (int i = 1; i <= n; ++i)
    if (a[i] == m) ++ans;
  for (int i = n; i; --i) {
    if (a[i] == m - 1) ++ans;
    else if (a[i] == m) break;
  }
  return ans;
}
} // namespace Part2

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  m = *std::max_element(a + 1, a + 1 + n);
  if (m == 1) return void(std::cout << n << '\n');
  std::cout << (Part1::solve() + Part2::solve()) % kMod << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> cid >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}
题解 > dp
#题解 #adhoc #dp #单调栈
P11835 [省选联考 2025] 封印 题解
https://sobaliuziao.github.io/2025/03/10/post/abdc5d6e.html
作者
Egg_laying_master
发布于
2025年3月10日
许可协议