大师 - 题目列表

形式化题目

给定长度为 $n$ 的非负整数序列 $h_1, h_2, \dots, h_n$ .

从下标 $1..n$ 中选一个非空子集 $S = \{s_1 < s_2 < \dots < s_m\}$ , 按原顺序读出高度 $h_{s_1}, \dots, h_{s_m}$ . 若存在整数 $d$ 使 $h_{s_{t+1}} - h_{s_t} = d$ 对所有 $1 \leqslant t < m$ 成立, 则称该子集美观.

要求统计美观子集的个数, 对 $998244353$ 取模. 约定 $m = 1$ 与 $m = 2$ 恒美观, $m = 0$ 不算.

注意 $d$ 可以为负、可以为 $0$ ; 同一组高度出现在不同下标位置时算不同方案.

解法路线

最直白的做法是枚举全部 $2^n$ 个子集再逐个检查, 这只能做到 $n \leqslant 20$ . 要跨过 $n = 10^3$ , 需要把"结构相同的方案合并起来一起数".

关键观察是: 固定公差 $d$ 之后, 合法性只看相邻被选项的高度差. 于是状态里可以由"结尾那一项 + 公差"刻画, 也可以换成"结尾那一项 + 它前面那一项". 两种刻画都给出 $O(n^2)$ 的转移, 区别在空间: 前者要开公差维, 依赖值域上界 $v$ ; 后者把公差换成高度查询, 用一次分桶把值域维消掉.

下面按题面的真实档位组织主线, 每层都能对上题面里的一个约束. 第四档「高度本身是等差数列」是结构受限的特例分支, 列在正解之后.

层次	适用约束	做法	复杂度	相对前层的推进
暴力枚举	$n \leqslant 20$ (题面前 30%)	01 序列递归枚举所有下标子集, 叶子处检查相邻高度差是否全等	时间 $O(2^n \cdot n)$ , 空间 $O(n)$	基线
按公差建桶的 DP	$n \leqslant 10^3$ 且 $v \leqslant 2 \times 10^3$ (题面前 60%)	状态 `dp[i][d]` = 以 $i$ 结尾、公差 $d$ 、长度 $\geqslant 2$ 的个数; 负数公差用 `d + v` 平移到下标	时间 $O(n^2)$ , 空间 $O(nv)$	用「结尾 + 公差」取代逐方案枚举, 把 $2^n$ 压成 $n^2$ ; 代价是空间挂上了值域
按上一项位置建桶的 DP(正解)	$n \leqslant 10^3$ , $v \leqslant 2 \times 10^4$ (题面 100%)	状态 `f[i][j]` = 最后两项是 $j, i$ 的个数; 固定中间项 $j$ 时把 $f[j][k]$ 按高度分桶, 右侧查 `2h[j] - h[i]`	时间 $O(n^2)$ , 空间 $O(n^2 + v)$	时间同阶. 用 $h_k = 2h_j - h_i$ 这个换元把「公差」这一维换成一次高度查询, 取消 $v$ 有界的假设

「另外 20%: 所有高度构成等差数列」与上面三层互不包含: 它的 $n$ 可以是 $10^3$ , 但结构受限使答案有闭式解. 它是特例分支, 见后文单独一节, 不串进主线.

正式主解是第三层, 代码为 main.cpp(C++17)与 main.py(同算法 Python 实现).

暴力解法

适用范围

$n \leqslant 20$ (题面前 30%).

思路

一个方案就是一个下标子集, 所以直接枚举全部子集: 每座塔"留"或"不留"两个选择, 用 01 序列递归把 $2^n$ 种选择序列全生成出来, 到叶子再整体检查.

choose[i] 记录第 $i$ 座塔的选择, 1 为留下, 0 为不留.
dfs(dep) 只决定第 dep 座塔的取值, 然后递归到下一层.
dep == n + 1 时方案完整, 调用 check_and_count():

按顺序取出所有 choose[i] == 1 的位置, 记项数 $m$ ;
$m = 0$ 不美观, 直接返回;
$m \leqslant 2$ 一定美观, 计数加一;
$m \geqslant 3$ 时取前两项高度差作为 $d$ , 逐对检查相邻高度差是否都等于 $d$ , 全部相等才计数.

把合法性检查放在叶子、而不在递归参数里提前剪枝, 是为了让"每层只做一个选择"这件事保持清楚.

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-26 13:45
 * update_at: 2026-10-26 16:36
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 用 01 序列递归枚举所有下标子集，到叶子再检查选出的高度是否构成等差数列。
// 复杂度 O(2^n * n)，只适合 n <= 20 的数据。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 25; // 只能枚举到 n = 20 左右

int n;
int h[MAXN];      // h[i]: 第 i 座塔的高度, 下标从 1 开始
int choose[MAXN]; // choose[i]: 第 i 座塔留在地上为 1, 缩到地下为 0
ll ans;           // 美观方案数

// 检查当前 choose[1..n] 选出的高度是不是等差数列, 是则把答案加一。
void check_and_count() {
    int first = 0; // 选出的第一个下标
    int second = 0;
    int cnt = 0;   // 选出了几座塔
    for (int i = 1; i <= n; i++) {
        if (choose[i] == 0) {
            continue;
        }
        cnt++;
        if (cnt == 1) {
            first = i;
        } else if (cnt == 2) {
            second = i;
        }
    }
    if (cnt == 0) {
        return; // 一座都不留不算美观
    }
    if (cnt <= 2) {
        ans++;  // 只留一座或两座塔一定是等差数列
        return;
    }
    // 长度 >= 3 时, 相邻高度差是否全部相等就是判定标准
    int d = h[second] - h[first];
    int last = second;
    for (int i = second + 1; i <= n; i++) {
        if (choose[i] == 0) {
            continue;
        }
        if (h[i] - h[last] != d) {
            return;
        }
        last = i;
    }
    ans++;
}

// 这一层决定第 dep 座塔留不留下: 0 不留, 1 留下。
void dfs(int dep) {
    if (dep > n) {
        check_and_count();
        return;
    }
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs(dep + 1);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &h[i]);
    }
    dfs(1);
    printf("%lld\n", ans);
    return 0;
}

复杂度与瓶颈

时间 $O(2^n \cdot n)$ : $2^n$ 个叶子, 每个叶子线性检查. $n = 20$ 时约 $2 \times 10^7$ 次基本操作.
空间 $O(n)$ .

瓶颈很清楚: 方案数是 $2^n$ 量级. 样例 2 的 $n = 100$ 就已经是 $2^{100}$ . 而这些方案里有大量"前缀相同、只是后面接得不同"的重复结构, 逐方案枚举完全没有利用它们.

子任务解法: 按公差建桶的 DP

适用范围

$n \leqslant 10^3$ 且 $v \leqslant 2 \times 10^3$ (题面前 60%).

思路

先看暴力里浪费在哪里. 枚举子集时, 判断"能不能接下一座塔"只需要知道两件事: 已选序列的最后一项位置, 以及当前公差. 加上这一个观察, 就能把"枚举方案"改成"数方案".

状态: dp[i][d] 表示以第 $i$ 座塔结尾、公差为 $d$ 、长度 $\geqslant 2$ 的等差子序列个数.

转移: 枚举倒数第二项的下标 $j < i$ . 合法的 $j$ 必须满足 $h_i - h_j = d$ .

dp[i][d] = \sum_{j<i,\ h_i - h_j = d} \bigl(dp[j][d] + 1\bigr)

右边的 $+1$ 是"只取 $h_j$ 与 $h_i$ 这两座塔"这一种长度 2 的方案; 其余是把"以 $j$ 结尾、公差也等于 $d$ "的每条序列接上 $h_i$ .

长度 1: 每座塔单独都算一种方案, 答案初值取 $n$ .

负数公差: $d = h_i - h_j$ 落在 $[-v, v]$ . 数组下标不能为负, 于是统一平移 $v$ , 用 d + v 当第二维下标, 值域宽度为 $2v + 1$ .

用一个小例子 1 2 3 4(下标 $1..4$ )走一遍. 表中每行是算完 $dp[i][\cdot]$ 之后被写过的那些 $d$ :

$i$	$h_i$	枚举 $j$ 得到的 $(d, \text{贡献})$	算完后 $dp[i]$ 的非零项
1	1	无	空
2	2	$j=1$ : $d=1$ , 贡献 $dp[1][1]+1 = 1$	$\{1: 1\}$
3	3	$j=1$ : $d=2$ , 贡献 $1$ ; $j=2$ : $d=1$ , 贡献 $dp[2][1]+1 = 2$	$\{2: 1,\ 1: 2\}$
4	4	$j=1$ : $d=3$ , 贡献 $1$ ; $j=2$ : $d=2$ , 贡献 $1$ ; $j=3$ : $d=1$ , 贡献 $dp[3][1]+1 = 3$	$\{3:1,\ 2:1,\ 1:3\}$

观察重点有两个:

同一个公差 $d = 1$ 在相邻两行都被命中: $dp[3][1]$ 由 $dp[2][1] + 1 = 2$ 得到, $dp[4][1]$ 又由 $dp[3][1] + 1 = 3$ 得到. 这就是等差链在状态里"接长"的过程, 也是逐方案枚举完全忽略掉的那部分结构.
第 4 行同时出现了三个不同的公差 $3, 2, 1$ , 说明一个结尾位置可以同时延续好几条不同的链; 状态必须带上公差才能把它们分开.

答案 $= n + \sum_{i,d} dp[i][d] = 4 + (1 + 3 + 5) = 13$ . 按长度拆开是长度 1 的 4 个、长度 2 的 6 个、长度 3 的 2 个、长度 4 的 1 个, 合计 13.

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-26 13:45
 * update_at: 2026-10-26 16:36
 */
// subtask_nv.cpp：按公差建桶的 DP，直接 dp[i][d] 记录公差 d，适用于 v <= 2e3 的 60% 档。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 998244353;
const int MAXN = 1005;  // n <= 1000
const int MAXV = 2005;  // 本题档位的高度上限 v <= 2e3, 负数公差靠偏移量 v 平移

ll n;
ll h[MAXN];       // h[i]: 第 i 座塔的高度, 下标从 1 开始
ll v;              // v = 最高的塔
ll dp[MAXN][2 * MAXV];  // dp[i][d + v]: 以第 i 座塔结尾、公差为 d 且长度 >= 2 的等差子序列个数

void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> h[i];
        v = max(v, h[i]);
    }
}

void solve() {
    ll ans = n; // 长度 1 的子序列一定等差
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            ll d = h[i] - h[j];        // 公差可为负, 下标要加偏移 v
            // 前一项是 h[j] 的等差子序列接上 h[i], 再加上只取 j, i 两项这一种
            ll ways = dp[j][d + v] + 1;
            dp[i][d + v] = (dp[i][d + v] + ways) % MOD;
            ans = (ans + ways) % MOD;
        }
    }
    cout << ans % MOD << '\n';
}

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

    read_input();
    solve();
    return 0;
}

复杂度与瓶颈

时间 $O(n^2)$ : 枚举 $j < i$ 的二元组, 每次 $O(1)$ .
空间 $O(n \cdot 2v)$ : 状态里带着公差维.

$v = 2 \times 10^3$ 时是 $4 \times 10^6$ 个 int, 可以接受. 但 $v$ 一旦涨到 $2 \times 10^4$ , 状态数变成 $4 \times 10^7$ , 既慢又占内存.

问题出在状态设计: 公差 $d$ 的取值个数是 $2v+1$ , 这个维度把值域带进了状态. 要跨过这一档, 得让状态里不出现 $d$ .

正解

关键观察

上式里"找公差为 $d$ 的上一个状态"是一个二维匹配条件: 既要位置在前, 又要高度差恰好等于 $d$ . 换个角度, 把它写成关于某一项的等式.

固定中间项 $j$ , 要求前一项 $h_k$ 与后一项 $h_i$ 关于 $h_j$ 对称:

h_j - h_k = h_i - h_j \quad \Longleftrightarrow \quad h_k = 2h_j - h_i

于是"待查的东西"从一个公差值 $d$ 变成了一个确定的高度 $2h_j - h_i$ . 高度可以当桶下标直接用, 公差这一维就消失了.

思路

状态: f[i][j]( $j < i$ ) 表示最后两项是第 $j$ 座和第 $i$ 座塔的等差子序列个数, 包含"只有这两项"这一种.

转移: 枚举倒数第三项的下标 $k < j$ , 它必须满足上面那个对称条件.

f[i][j] = 1 + \sum_{k<j,\ h_k = 2h_j - h_i} f[j][k]

右边的 $1$ 是长度 2 的方案 $\{j, i\}$ ; 其余是把"最后两项是 $k, j$ "的每条序列接上 $h_i$ .

为什么不会重复计数: 状态里写死了"最后两项是哪两个下标". 一个长度 $\geqslant 2$ 的子序列只有唯一一对最后两项, 所以它只被一个状态统计; 各状态对应的序列集合互不相交. 长度 $1$ 的方案单独用 $n$ 计.

长度 2 与长度 1 的处理: 长度 2 由初值 $1$ 承担, 对每个 $i > j$ 恰好计一次, 合计 $\binom{n}{2}$ 个, 与长度 2 子集数一致. 长度 1 由答案初值 $n$ 承担.

每个 $j$ 只做一次分桶

照上式硬算, 每个 $(i,j)$ 要扫一遍 $k < j$ , 总时间 $O(n^3)$ . 观察一下被求和的那批 $f[j][k]$ : 固定 $j$ 之后, 它们怎么分组只由 $h_k$ 决定, 与 $i$ 无关. 所以把分组提到 $i$ 的循环外面, 做一次就够.

固定 $j$ 后按三步走:

建桶: 对所有 $k < j$ , 做 bucket[h_k] += f[j][k]. 代价 $O(j)$ .
查询: 对所有 $i > j$ , 需要的是 bucket[2h_j - h_i], 一次取值就是答案, 再 +1. 代价 $O(n - j)$ .
清桶: 本轮写过的桶位置清零, 交给下一个 $j$ .

总时间 $\sum_{j} \bigl(j + (n - j)\bigr) = O(n^2)$ .

用同一个例子 1 2 3 4 走一遍. 表中每行是固定 $j$ 之后建好的桶, 以及右侧每个 $i$ 查到的结果:

$j$	$h_j$	建好的桶 $h_k \to \sum f[j][k]$	查询 $i$ 得到的 $(h_i,\ 2h_j - h_i,\ f[i][j])$
1	1	空	$(2,\ 0,\ 1)$ , $(3,\ -1,\ 1)$ , $(4,\ -2,\ 1)$
2	2	$\{1: 1\}$	$(3,\ 1,\ 2)$ , $(4,\ 0,\ 1)$
3	3	$\{1: 1,\ 2: 2\}$	$(4,\ 2,\ 3)$
4	4	$\{1:1,\ 2:1,\ 3:3\}$	无右侧项

观察重点有三个:

第 $j = 2$ 行: 桶里只有高度 $1$ (来自 $f[2][1] = 1$ ). 查询 $i = 3$ 需要的正好是 $2 \times 2 - 3 = 1$ , 命中, 得 $f[3][2] = 1 + 1 = 2$ , 对应 $\{2,3\}$ 与 $\{1,2,3\}$ 两条链.
第 $j = 3$ 行: 桶是 $\{1: 1,\ 2: 2\}$ , 其中高度 $2$ 下攒的 $2$ 就是 $f[3][2]$ . 查询 $i = 4$ 需要 $2 \times 3 - 4 = 2$ , 命中, 得 $f[4][3] = 1 + 2 = 3$ , 即 $\{3,4\}$ 、 $\{2,3,4\}$ 、 $\{1,2,3,4\}$ . 长度 4 的方案只在这里出现.
第 $j = 1$ 行: 桶是空的, 所以查到的 $f$ 全是 $1$ . $j = 1$ 时不存在倒数第三项, 只能是长度 2, 与结果一致.

need 为负的格子(如 $2h_1 - h_3 = -1$ )天然落空, 因为高度不可能为负. 这也是查桶前判界不能省的直接原因.

答案 $= n + \sum_{i>j} f[i][j] = 4 + (3 + 3 + 3) = 13$ , 与上一层相同.

顺序不能换

建桶必须先于查询, 而且桶里只能装 $k < j$ 的状态. 若边查边往桶里塞, 就会把 $k \geqslant j$ 的项混进来, 递推条件被破坏. 这就是代码里"建桶"和"查询"分成两个独立循环的原因.

判界

$2h_j - h_i$ 可能为负(当 $h_i > 2h_j$ ), 也可能超过 $v$ . 这两种情况对应的桶一定是空的, 直接跳过; 但访问数组前必须判界, 否则越界.

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-26 13:45
 * update_at: 2026-10-26 16:36
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 998244353;
const int MAXN = 1005;   // n <= 1000
const int MAXH = 20000;  // 电塔高度上限 v <= 2e4

ll n;
ll h[MAXN];      // h[i]: 第 i 座塔的高度, 下标从 1 开始
ll f[MAXN][MAXN]; // f[i][j] (i > j): 最后两项是第 j 座和第 i 座塔的等差子序列个数, 含长度 2
ll bucket[MAXH + 1]; // bucket[v]: 固定中间项 j 时, 左侧高度恰为 v 的所有 f[j][k] 之和

void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> h[i];
    }
}

void solve() {
    ll ans = n; // 只留一座塔的方案(长度 1)一定等差, 先把它们计入答案
    for (int j = 1; j <= n; j++) {
        // 把中间项 j 左侧所有 f[j][k] 按高度 k 所在的高度分桶, 后面按需要的高度直接取
        for (int k = 1; k < j; k++) {
            bucket[h[k]] = (bucket[h[k]] + f[j][k]) % MOD;
        }
        for (int i = j + 1; i <= n; i++) {
            // 公差 d = h[i] - h[j], 所以 j 前面那一项的高度只能是 2*h[j] - h[i]
            ll need = 2 * h[j] - h[i];
            ll ways = 1; // 只保留第 j 座和第 i 座塔, 长度 2 也算一种方案
            if (need >= 0 && need <= MAXH) {
                ways += bucket[need];
            }
            ways %= MOD;
            f[i][j] = ways;
            ans = (ans + ways) % MOD;
        }
        for (int k = 1; k < j; k++) { // 清空本轮写过的桶, 交给下一个中间项使用
            bucket[h[k]] = 0;
        }
    }
    cout << ans % MOD << '\n';
}

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

    read_input();
    solve();
    return 0;
}

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-26 13:45
# update_at: 2026-10-26 13:45

import sys

MOD = 998244353


def count_arithmetic(heights: list[int]) -> int:
    """统计所有等差子序列(长度 1、2 也计入)。按中间项 j 分桶, 右侧查询 O(1)。"""
    n = len(heights)
    # f[i][j](i > j): 最后两项是 heights[j], heights[i] 的等差子序列个数, 含长度 2
    f = [[0] * n for _ in range(n)]
    ans = n                      # 长度 1 的子序列一定等差
    for j in range(n):
        # 固定中间项 j, 把左侧所有 f[j][k] 按高度分桶: 高度 -> 这些 f 之和
        bucket: dict[int, int] = {}
        for k in range(j):
            v = heights[k]
            bucket[v] = (bucket.get(v, 0) + f[j][k]) % MOD
        middle = heights[j]
        for i in range(j + 1, n):
            # 公差 d = heights[i] - middle, 前一项高度必须是 2*middle - heights[i]
            ways = bucket.get(2 * middle - heights[i], 0) + 1   # +1 是只取 j, i 两项
            f[i][j] = ways % MOD
            ans += ways
        ans %= MOD
    return ans % MOD


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    heights = [next(data) for _ in range(n)]
    print(count_arithmetic(heights))


if __name__ == "__main__":
    solve()

复杂度

时间 $O(n^2)$ : 每轮 $j$ 的建桶 $O(j)$ 加查询 $O(n-j)$ , 求和为 $O(n^2)$ .
空间 $O(n^2 + v)$ : f 是 $n \times n$ 的 int 表, bucket 是长度 $v + 1$ 的计数数组.

与上一层的差别只在空间: 时间同为 $O(n^2)$ , 但状态里不再出现公差维, 于是 $v$ 不再受 $O(n)$ 量级的限制. $n = 1000$ 时 f 是 $10^6$ 个 int(约 4 MB), bucket 是 20001 个 long long(约 160 KB).

实测满规模( $n = 1000$ , 高度随机取 $[0, 2 \times 10^4]$ )为 11 ms / 4.9 MB; Python 版按同算法实现, 用 dict 代替定长桶, 峰值 27 MB, 在 3 倍时限口径(3000 ms)下最大 391 ms.

在 $n$ 取 250 / 500 / 1000 时分别测得 4 / 7 / 14 ms, $n$ 翻倍时间约翻倍, 与 $O(n^2)$ 相符.

子任务解法: 所有高度构成等差数列(特例分支)

题面「另外 20%: 所有电塔的高度构成一个等差数列」这一档与上面三层互不包含, 它不靠缩小 $n$ 也不靠缩小 $v$ , 而是结构受限使答案可以直接算. 所以它是一条特例分支, 不构成主线的第四层.

适用范围

$h_i = h_1 + (i-1)\Delta$ 对所有 $i$ 成立(某个固定 $\Delta$ ).

思路

若 $\Delta = 0$ , 所有高度相同, 任意非空子集都构成公差为 $0$ 的等差数列, 答案是 $2^n - 1$ .
若 $\Delta \ne 0$ , 选出 $m$ 座塔时, 相邻高度差都是 $\Delta$ 的整数倍, 而"倍数是否全相等"恰好等价于"下标差是否全相等". 于是合法的下标子集正好是下标 $1..n$ 的等差数列.
长度为 $m$ 、下标公差为 $q$ 的下标等差数列, 首项可以取 $1, 2, \dots, n - (m-1)q$ , 共 $n - (m-1)q$ 个.

\text{答案} = n + \sum_{q \geqslant 1} \sum_{\substack{m \geqslant 2 \\ (m-1)q \leqslant n-1}} \bigl(n - (m-1)q\bigr)

这个闭式解与 $v$ 无关, 与这一档之外的实现完全独立. 正文给出它是为了说明: 这一档不能用" $n$ 更小"来描述, 它是一条独立分支.

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-26 13:45
 * update_at: 2026-10-26 16:36
 */
// subtask_ap.cpp：题面「另外 20%：所有电塔高度本身构成等差数列」这一档的闭式解。
// 这一档不属于正解主线，只是利用「高度限制死了一个固定公差」把计数变成数下标等差数列。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 998244353;
const int MAXN = 1005; // n <= 1000

ll n;
ll h[MAXN]; // h[i]: 第 i 座塔的高度, 下标从 1 开始

ll pow_mod(ll base, ll exp) {
    ll result = 1 % MOD;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) {
            result = result * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> h[i];
    }
}

void solve() {
    // 公差为 0: 高度全相同, 任意非空子集都等差
    bool all_equal = true;
    for (int i = 2; i <= n; i++) {
        if (h[i] != h[1]) {
            all_equal = false;
        }
    }
    if (all_equal) {
        cout << (pow_mod(2, n) - 1 + MOD) % MOD << '\n';
        return;
    }

    // 公差不为 0: 选出的高度等差 <=> 选出的下标等差, 于是只需数 1..n 里的下标等差数列
    ll ans = n; // 长度 1 的方案
    for (ll q = 1; q <= n - 1; q++) {          // q: 下标公差的绝对值
        for (ll len = 2; (len - 1) * q <= n - 1; len++) { // len: 选出的项数
            // 首项可取 1..n-(len-1)q, 每换一个首项就得到一个新的下标等差数列
            ans = (ans + n - (len - 1) * q) % MOD;
        }
    }
    cout << ans % MOD << '\n';
}

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

    read_input();
    solve();
    return 0;
}

复杂度与瓶颈

时间 $O(n^2)$ (实际内层总次数是 $\sum_{q} \frac{n}{q} \approx n \ln n$ , 按上界记 $O(n^2)$ ).
空间 $O(n)$ .

这一层没有可推进的瓶颈: 它依赖「整体等差」这个额外条件, 条件一旦去掉就要回到主线. 它只说明题面这一档为什么能用完全不同的做法.

这一档已用 $n \leqslant 12$ 的四种序列(递增、递减、全等高、公差 3)与 $2^n$ 枚举逐一对齐, 并且对等差形状的随机数据与正解对拍 100 组通过.

总结

题目的核心是把"枚举方案"改成"数方案". 固定公差后, 合法性只取决于相邻两项的高度差, 于是"结尾位置 + 公差"成为充分的状态.
两种等价的状态刻画都给出 $O(n^2)$ 的转移: 用公差做第二维要开 $2v$ 的桶, 空间挂上值域; 用「上一项的位置」做第二维, 再借 $h_k = 2h_j - h_i$ 把公差换成一个确定的高度查询, 空间就只与 $n$ 有关.
每轮 $j$ 把左侧状态按高度分桶一次, 是本题把 $O(n^3)$ 降到 $O(n^2)$ 的关键实现手段. 分桶的三个动作(建桶、查询、清桶)顺序固定, 且桶里只能装 $k < j$ 的项.
三个容易出错的细节: 长度 1 与长度 2 单独计; 负数公差在第一种写法里要平移下标; $2h_j - h_i$ 可能为负或超界, 查桶前必须判界.
「高度本身是等差数列」这一档是结构受限的特例分支, 有独立闭式解, 不与主线构成递进关系.

大师

目录

形式化题目

解法路线

暴力解法

适用范围

思路

代码

复杂度与瓶颈

子任务解法: 按公差建桶的 DP

适用范围

思路

代码

复杂度与瓶颈

正解

关键观察

思路

每个 jjj 只做一次分桶

顺序不能换

判界

代码

复杂度

子任务解法: 所有高度构成等差数列(特例分支)

适用范围

思路

代码

复杂度与瓶颈

总结

每个 $j$ 只做一次分桶