问题编号： 202104-4
问题名称：校门外的树
时间限制： 1.0s
内存限制： 512.0MB
问题说明：
问题描述
x学校最近打算美化校园环境。 这期间，由于修理了地铁，在x学校大门外种植的行道树全部被拆除了。 现在，x校打算再种几棵树，为校园增添绿意。
x学校门外的路是东西走向的，我们可以把它看成一个数轴。 这个轴上有n个障碍物。 例如电线杆等。 虽然障碍物会影响树木的生长，但障碍物并不一定会被随意清除，所以在x学校规定不能在障碍物的位置种树。 n个障碍物的坐标都是整数； 以东为正方向，n障碍物的坐标从西到东依次分别为a1、a2、…、an。 x学校打算在[a1，an]之间种一些树，让这些树看起来很美。
x学校希望在一定范围内，树是等间隔的。 更具体地说，使[a1，an]为几个区间[ap1，ap2，…、[apm-1，apm，1=p1<； p2<； <； 如果分为pm=n，则根据每个区间至少需要一种[api，API1]的区间，公差也就是树的间隔可以不同。
例如，如果障碍物位于0、2、6这三个位置，则可以选择分别在0、2和2、6种树，也可以选择在0、6等间距种树。 在[ 0，2 ]和[ 2，6 ]分别种树时，必须在坐标1处种树，以便每个区间至少种一棵树； 另一方面，[ 2，6 ]的树可以以1的间隔种植，也可以以2的间隔种植。 下图显示了这两种美丽的植树方案。 橙色的圆表示障碍物，绿色的圆表示需要在这个位置植树。 箭头上的数字表示种这棵树时对应的间隔是多少。
在区间[ 0，2 ]和[ 2，6 ]分别以1和2的间隔种树很美
在区间[ 0，2 ]和[ 2，6 ]分别以1的间隔种树也很美
另一方面，如果选择在[ 0，6 ]区间等间隔种树，我们只能每隔3分钟种树。 即使选择间隔1或间隔2，也需要在坐标2处种树，因为在这个位置已经有障碍物。 下图分别显示间隔为3、2、1时的植树情况，红色箭头表示不能在此植树。
相对于区间[ 0，6 ]以3的间隔种树是美丽的
相对于区间[ 0，6 ]以2的间隔种树并不美
相对于区间[ 0，6 ]以1的间隔种树也不美观
通常，给定某个区间[al，ar]，对于树坐标的集合t[al，ar][TZ]，归纳定义t在[al，ar]中是美丽的：
1 .如果t、t{ al，al 1，…，ar}=，且存在公差d1，使得T{al，ar}的元素按照从小到大的顺序排序后，能够构成公差d的等差数列(该等差数列的最初
T{al，al 1，…，ar}=，为了使tal，am (在[al，am]中变漂亮且T(am，ar )在[am，ar]中变漂亮而下标m ) m () 并购； r )存在时
根据这个定义，空集在任意区间都是不美丽的，另外，如果通过下标I制作aiT的话，t一定是不美丽的。
我们说两种植树的方案本质上不同，而且只有两种方案中，植树的坐标集合不同。 请帮我x校对[a1，an]求所有本质不同的漂亮植树方案。 当然，方案可能很多，所以只需输出对109 7的总方案数取模的结果。
输入格式
的第一行包含一个正整数n，表示障碍物的数量。
的第二行包含n个非负整数a1，an，表示每个障碍物的坐标。
对I=1，2，…，n-1，ai<； 保证是ai 1。
输出格式
输出非负整数，表示不同美观植树方案数量对109 7的取模结果。
样例输入
3
0 2 6
样例输出
3
样例说明
这个小组是在标题说明中提到的小组。
样例输入
11
0 10 20 30 40 50 60 70 80 90 100
样例输出
256507
样例输入
333
33 44 67 210 528 762 873 984 1234 1466 1739 2859 3421 4061 4598 5172 5201 5220 5261 5322 5389 5559 6670 7070 7898 8079 8129 8192 8616 8641 8806 9559 95 85 9750 10263 10627 10674 10692 10903 11649 11885 12179 12307 12743 13173 13352 13389 13
496 13611 15292 15321 16018 16327 16415 16959 16972 17499 17617 17786 18476 18966 19239 19498 19875 20312 20392 21603 21620 21730 21967 21972 21999 22015 22590 22775 23709 23839 24165 24408 24595 25160 25479 25812 26482 27328 28101 28297 28305 28342 28557 28986 29110 29401 29765 30292 30493 30739 31027 31201 31218 31414 32089 32759 32770 32777 32815 32877 32890 33297 33457 33603 33757 33866 34498 34525 34659 34679 34861 34870 34997 35311 35846 36411 36457 36738 36902 37940 38228 40156 40320 40705 40737 40803 41066 41443 41460 41954 41968 42040 42062 42099 43281 43320 43527 43537 43587 43729 44750 44822 45655 45769 46109 46525 47060 47128 47999 48635 48887 48981 49366 49424 49524 50546 50580 50689 51332 51861 51943 52097 52702 53009 53067 53397 53526 53901 54280 54399 54801 55535 55592 55740 55843 56110 56428 56552 56682 56848 57179 57688 57797 57847 57959 58330 58831 59553 59699 59884 59939 61233 61636 61732 61908 62145 62549 62649 62740 62912 62971 63053 64312 64322 64412 64816 64845 64873 64923 64976 65023 65166 65496 66065 66491 66803 66941 67081 68331 68336 68360 68476 69179 69719 69758 69948 70072 70544 70598 70990 71014 71454 71687 71743 71958 72282 72384 72456 72985 73327 74325 75046 75097 76647 77062 77088 77431 77553 77673 77753 78217 78518 78564 79565 79588 79686 80275 80939 81052 81348 81386 81440 81589 81610 81793 82408 82801 82836 83239 83466 83610 83867 83943 84441 84467 85248 85305 85554 85565 85758 86251 86603 86743 87323 87565 87824 87833 88265 88309 89178 89509 89618 89699 89708 90331 90359 90878 90902 91449 92284 92374 92549 92609 93609 94345 94934 95140 95475 95733 95985 95995 96270 96641 96807 97003 97632 98160 98677 98853 98943 99037 99055 99075 99185 99395 99592样例输出
7094396
评测用例规模与约定
对于10%的数据，保证n=2；
对于30%的数据，保证n≤10；
对于60%的数据，保证n≤100，ai≤1000；
对于100%的数据，保证2≤n≤1000，0≤ai≤100,000，且至少存在一种美观的种树方案。
问题链接：CCF202104-4 校门外的树
问题简述：（略）
问题分析：打表预处理。
程序说明：（略）
参考链接：（略）
题记：（略）
100分的C++语言程序如下：
/* CCF202104-4 校门外的树 */#include <bits/stdc++.h>//#define DEBUGusing namespace std;const int MOD = 1e9 + 7;const int N = 1000 + 1;const int AI = 100000 + 1;int n, a[N];long long f[N];bool flag[AI];int main(){ vector<int> v[AI]; for (int i = 1; i < AI; i++) for (int j = 2 * i; j < AI; j += i) v[j].push_back(i);#ifdef DEBUG for (int i = 1; i <= 20; i++) { printf("Case #%d: ", i); for (int j = 0; j < (int)v[i].size(); j++) printf("%d ", v[i][j]); printf("n"); }#endif scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); f[1] = 1; for (int i = 2; i <= n; i++) { memset(flag, false, sizeof flag); for (int j = i - 1; j >= 1; j--) { int d = a[i] - a[j], cnt = 0; for (int k:v[d]) if (!flag[k]) cnt++, flag[k] = true; flag[d] = true; f[i] = (f[i] + f[j] * cnt) % MOD; } } printf("%lldn", f[n]); return 0;}AC的C++语言程序如下：