问题描述
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,api+1)内需要至少种一棵树，且该区间内种的树的坐标连同区间端点api,api+1应该构成一个等差数列。不同区间的公差，也就是树的间隔可以不相同。
对区间[0,2)和[2,6)分别以1的间隔种树也是美观的
对区间[0,6)以1的间隔种树也是不美观的
一般地，给定一个区间[al,ar)，对于树的坐标的集合 T（al,ar)（TZ），归纳定义T在[al,ar)上是美观的：
根据这一定义，空集在任意区间上都不是美观的；另外，如果存在下标i使得ai∈T ，那么T一定不是美观的。
我们称两种种树的方案是本质不同的，当且仅当两种方案中，种树的坐标集合不同。请帮助 X 校对[a1,an)求出所有本质不同的美观的种树方案。当然，由于方案可能很多，你只需要输出总方案数对109+7取模的结果。
输入格式
输入的第一行包含一个正整数n，表示障碍物的数量。
输入的第二行包括n个非负整数a1,…,an，表示每个障碍物的坐标。
保证对i=1,2,…,n-1，ai＜ai+1。
输出格式
输出一个非负整数，表示本质不同的美观的种树方案的数量对109+7取模的结果。
样例输入
样例输出
3
样例说明
这组样例即为题面描述中提到的那组。
样例输入
样例输出
样例输入
样例输出
评测用例规模与约定
对于10%的数据，保证n=2；
对于30%的数据，保证n≤10；
对于60%的数据，保证n≤100，ai≤1000；
对于100%的数据，保证2≤n≤1000，0≤ai≤100,000，且至少存在一种美观的种树方案。
问题链接：CCF-4 校门外的树
问题简述：（略）
问题分析：打表预处理。
程序说明：（略）
参考链接：（略）
题记：（略）
100分的C++语言程序如下：
/* CCF-4 校门外的树 */ #include
AC的C++语言程序如下：
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/226130.html原文链接：https://javaforall.net
