校门外的树

GitHub跳转原题关系图 Canvas 关系图返回列表

预处理距离因子，动态标记内部障碍阻塞的公差并进行区间划分 DP。

OJ: shumeng

题目 ID: CSP202104D

难度:提高+/省选-

标签:动态规划数论因数计数

日期: 2026-07-31 16:21

形式化题目

数轴上有 $n$ 个障碍物，坐标 $a_1<a_2<\dots<a_n$ ，障碍物位置不能种树。把 $[a_1,a_n)$ 划分成若干区间 $[a_{p_i},a_{p_{i+1}})$ ，每个区间内至少种一棵树，且区间内的树连同两端构成等差数列，不能落在内部障碍物上。统计本质不同的种树方案数，对 $10^9+7$ 取模。

思路

一段区间内的公差数

以 $a_l,a_r$ 为端点的一段中，公差 $d$ 必须满足两个条件：

$d$ 是距离 $a_r-a_l$ 的真因子，否则首尾无法同时成为等差数列的项；
$d$ 不能整除任意内部距离 $a_k-a_l$ （ $l<k<r$ ），否则等差树列会经过障碍物 $a_k$ 。

记满足条件的公差个数为 $ways(l,r)$ 。

区间划分 DP

设 $dp[r]$ 为处理到第 $r$ 个障碍物的方案数，按最后一段从 $l$ 到 $r$ 划分：

dp[r]+=dp[l]\cdot ways(l,r)。

固定左端点 $l$ 后从左到右枚举 $r$ 。把已成为内部障碍物的距离的所有因子标记为不可用，于是检查当前端点距离的因子时就能直接得到 $ways(l,r)$ 。因子表用调和级数预处理。

先看一个直接枚举公差并逐一检查障碍物的朴素解：

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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，枚举每段的全部公差，直接检查是否经过内部障碍物。
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

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

    int n;
    cin >> n;
    vector<int> position(n + 1);
    vector<long long> dp(n + 1);
    for (int i = 1; i <= n; i++) cin >> position[i];
    dp[1] = 1;
    for (int left = 1; left < n; left++) {
        for (int right = left + 1; right <= n; right++) {
            int distance = position[right] - position[left];
            // 枚举公差 step：必须是距离的真因子，且不经过任何内部障碍物
            int ways = 0;
            for (int step = 1; step < distance; step++) {
                if (distance % step) continue;
                bool valid = true;
                for (int middle = left + 1; middle < right; middle++) {
                    if ((position[middle] - position[left]) % step == 0) valid = false;
                }
                if (valid) ways++;
            }
            dp[right] = (dp[right] + dp[left] * ways) % MOD;
        }
    }
    cout << dp[n] << '\n';

    return 0;
}

代码

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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXA = 100000;
const long long MOD = 1000000007;

int n, position[MAXN];        // 障碍物坐标
int blocked[MAXA + 1];        // blocked[d] 记录把公差 d 标记为不可用的左端点，0 表示未标记
long long dp[MAXN];           // dp[r] 表示划分到第 r 个障碍物的方案数
vector<int> divisor[MAXA + 1]; // divisor[x] 为 x 的所有因数

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

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> position[i];
    // 用调和级数预处理所有数的因数
    for (int d = 1; d <= MAXA; d++) {
        for (int value = d; value <= MAXA; value += d) divisor[value].push_back(d);
    }

    dp[1] = 1;
    for (int left = 1; left < n; left++) {
        // 固定左端点 left，从左到右枚举右端点 right
        for (int right = left + 1; right <= n; right++) {
            int distance = position[right] - position[left];
            // ways(l,r)：距离的真因子中未被内部障碍物阻塞的公差个数
            int ways = 0;
            for (int i = 0; i < (int)divisor[distance].size(); i++) {
                int step = divisor[distance][i];
                if (step != distance && blocked[step] != left) ways++;
            }
            dp[right] = (dp[right] + dp[left] * ways) % MOD;
            // 当前右端点对后续右端点来说变成内部障碍物，标记其所有因数为不可用
            for (int i = 0; i < (int)divisor[distance].size(); i++) blocked[divisor[distance][i]] = left;
        }
    }
    cout << dp[n] << '\n';

    return 0;
}

复杂度

设最大坐标为 $A$ 。预处理因子为 $O(A\log A)$ ；DP 的总检查量等于所有端点距离的因子数，满足本题范围，空间复杂度为 $O(A+n)$ 。

总结

每个叶子区间的等差树列由端点和公差唯一确定，区间划分 DP 能按最后一段无重计数。因子标记把“是否撞上内部障碍物”的多重检查压缩为常数次数组判断。

图示解析

text

1
2
3
4
5固定左端点 l
|- 内部障碍距离的因子 -> 标记为不可用公差
`- 枚举右端点 r 的距离因子
   `- 未标记的真因子数 = ways(l,r)
      `- dp[r] += dp[l] * ways(l,r)

随着右端点右移，旧右端点才变成新的内部障碍物，因此在计算当前 ways 后再标记当前距离的因子。

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

X 校最近打算美化一下校园环境。前段时间因为修地铁，X 校大门外种的行道树全部都被移走了。现在 X 校打算重新再种一些树，为校园增添一抹绿意。

X 校大门外的道路是东西走向的，我们可以将其看成一条数轴。在这条数轴上有 $n$ 个障碍物，例如电线杆之类的。虽然障碍物会影响树的生长，但是障碍物不一定能被随便移走，所以 X 校规定在障碍物的位置上不能种树。 $n$ 个障碍物的坐标都是整数；如果规定向东为正方向，则 $n$ 个障碍物的坐标按照从西到东的顺序分别为 $a_1, a_2, \cdots, a_n$ 。X 校打算在 $[a_1, a_n]$ 之间种一些树，使得这些树看起来比较美观。

X 校希望，在一定范围内，树应该是等间隔的。更具体地说，如果把 $[a_1, a_n)$ 划分成一些区间 $[a_{p_1}, a_{p_2}),\cdots,[a_{p_{m-1}},a_{p_m})$ （ $1=p_1<p_2<\cdots<p_m=n$ ），那么每个区间 $[a_{p_i},a_{p_{i+1}})$ 内需要至少种一棵树，且该区间内种的树的坐标连同区间端点 $a_{p_i}, a_{p_{i+1}}$ 应该构成一个等差数列。不同区间的公差，也就是树的间隔可以不相同。

例如，如果障碍物位于 $0, 2, 6$ 这三处，那么我们可以选择在 $[0, 2)$ 和 $[2, 6)$ 分别种树，也可以选择在 $[0, 6)$ 等间隔种树。如果是分别在 $[0, 2)$ 和 $[2, 6)$ 种树，由于每个区间内至少要种一棵树，坐标 $1$ 上必须种树；而 $[2, 6)$ 上的树可以按照 $1$ 的间隔种下，也可以按照 $2$ 的间隔种下。下图表示了这两种美观的种树方案，其中橙色的圆表示障碍物，绿色的圆表示需要在这个位置种树，箭头上的数字表示种下这棵树时对应的间隔为多少。

而如果选择在 $[0, 6)$ 区间等间隔种树，我们只能以 $3$ 的间隔种树，因为无论是选择间隔 $1$ 或者间隔 $2$ ，都需要在坐标 $2$ 上种树，而这个位置已经有障碍物了。下图分别表示了间隔为 $3, 2, 1$ 时的种树情况，红色箭头表示不能在这里种树。

一般地，给定一个区间 $[a_l, a_r)$ ，对于树的坐标的集合 $T\subset(a_l, a_r)$ （ $T\subset\mathbb{Z}$ ），归纳定义 $T$ 在 $[a_l, a_r)$ 上是美观的：

如果 $T\ne\varnothing$ ， $T\cap {a_l, a_{l+1}, \cdots, a_r}=\varnothing$ ，并且存在一个公差 $d\geq 1$ ，使得 $T\cup{a_l, a_r}$ 中的元素按照从小到大的顺序排序后，可以构成一个公差为 $d$ 的等差数列（显然，这个等差数列的首项为 $a_l$ ，末项为 $a_r$ ），则 $T$ 在 $[a_l, a_r)$ 上是美观的；
如果 $T\cap {a_l, a_{l+1}, \cdots, a_r}=\varnothing$ ，并且存在一个下标 $m$ （ $l<m<r$ ），使得 $T\cap(a_l, a_m)$ 在 $[a_l, a_m)$ 上是美观的，且 $T\cap(a_m, a_r)$ 在 $[a_m, a_r)$ 上是美观的，则 $T$ 在 $[a_l, a_r)$ 上是美观的。

根据这一定义，空集在任意区间上都不是美观的；另外，如果存在下标 $i$ 使得 $a_i \in T$ ，那么 $T$ 一定不是美观的。

我们称两种种树的方案是本质不同的，当且仅当两种方案中，种树的坐标集合不同。请帮助 X 校对 $[a_1, a_n)$ 求出所有本质不同的美观的种树方案。当然，由于方案可能很多，你只需要输出总方案数对 $10^9+7$ 取模的结果。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$ ，表示障碍物的数量。

输入的第二行包括 $n$ 个非负整数 $a_1, \cdots, a_n$ ，表示每个障碍物的坐标。

保证对 $i=1, 2, \cdots, n-1$ ， $a_i < a_{i+1}$ 。

输出格式

输出到标准输出。

输出一个非负整数，表示本质不同的美观的种树方案的数量对 $10^9+7$ 取模的结果。

input1

1
23
0 2 6

output1

样例 1 解释

这组样例即为题面描述中提到的那组。

input2

1
211
0 10 20 30 40 50 60 70 80 90 100

output2

样例3

见题目文件区的 3.in 和 3.ans。

子任务

对于 $100\%$ 的数据，保证 $2\leq n \leq 1000, 0\leq a_i \leq 10^5$ ，且至少存在一种美观的种树方案。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n\le$	$a_i\le$
1	10	$2$	$10^5$
2	20	$10$	$10^5$
3	30	$100$	$1000$
4	40	$1000$	$10^5$