202104-4 校门外的树

思路：

这道题用DP是肯定的。但是应该从1维DP开始看起，这里的数据ai表示1e5也说明了使用二维DP是不行的。使用一维DP，用f[i]表示a0~a[i]的所有选法数量.状态分割为所有最后一个区间的左端点，这样就可以作到不重不漏

反思：

这道题其实讲实话不算难，但是自己在考场上以现在的熟练度应该还是很难写出来，估计就是10分走人的样子。自己的思路只能说状态表示想对了，但是状态划分不对，有了太多的重合。所以以后写DP还是这样想：状态标识-》状态划分-》状态转移方程。

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1005;
const int M = 1e5 + 5;
const int MOD = 1e9 + 7;
bool st[M];
int f[N];
vector<int> q[M];
int a[N];
int n;
int main(){
    for(int i = 1;i){
        for(int j = 2 * i;j < M;j += i){
            q[j].push_back(i);
        }
    }
    scanf("%d", &n);
    for(int i = 0;i){
        scanf("%d", &a[i]);
    }
    f[0] = 1;
    for(int i = 1;i){
        memset(st, false, sizeof(st));
        for(int j = i - 1;j >= 0;j--){
            int d = a[i] - a[j];
            int cnt = 0;
            for(auto t : q[d]){
                if(!st[t]){
                    cnt++;
                    st[t] = true;
                }
            }
            st[d] = true;
            f[i] = (f[i] + (long long)f[j] * cnt) % MOD;
        }
    }
    cout<1]<<endl;
    return 0; 
}