Link:
Official website:
http://118.190.20.162/view.page?gpid=T125
Acwing: https://www.acwing.com/problem/content/description/3417/

Question meaning: give the unequal points of N on the number axis in sequence and record it as sequence A. first divide the large interval [a[0],a[N-1]] into several sub intervals [li,ri), and then select several points on the sub interval, which are required to form an equal difference sequence with the end points of the interval. The end points cannot be used as the selected points. Ask how many sets of selected points are there.
Analysis: first of all, this is a limited selection problem. The selection problems we see are usually solved by dp, class dp and memory search. The idea of dp and memory search is to divide the problem into multiple stages, each stage will correspond to a state, and the states in the later stages should use the calculated states.
In the same way, this problem is divided into stages. First find the number of schemes containing a sequence of N numbers, and then find the number of schemes containing 2 numbers... And so on. Finally, find the one containing N numbers, which is the final answer.
Therefore, the i-th state of this question is the total number of schemes from the 0-th number to the i-th number, that is, dp[i]. One dimension can represent the state
After that, we need to see how to use the previous stage to calculate the state values of each stage. For the first state, it is the approximate number from the 0th number to the 1st number. For the i-th state, we can first divide the i-th state into the part calculated by dp[i-1], the part calculated by dp[i-2], and the part calculated by dp[0]. For example, when calculating the i-1st state, that is, DP When calculating the part of [i-1], since the scheme before i-1 will not affect the methods from i-1 to I, there are dp[i-1] methods from 0 to i-1, and the methods from i-1 to I have the divisor of a[i]-a[i-1], set as cnt, and the contribution to dp[i] is cnt*dp[i-1].
However, when calculating the contribution value obtained by dp[i-2], will the scheme from i-2 to I coincide with the scheme from i-1 to I? Note that to divide dp[i] into non intersecting sets and combine them into subsets of the complete set, we need to design our own division method. Our direction is to write a simple formula for the relationship between dp[i] and dp[0... i-1]. We have obtained that the contribution of dp[i-1] is dp[i-1]*cnt, we hope to find cnt from 0 to i-2.

Finally, we find that if the cnt of i-2 is set to the number of elements of the set containing divisors from i-2 to i and not from i-1 to i, we can divide the problem without repetition and omission. At the same time, the topic says that trees can not be planted where there are obstacles, so the schemes from i-2 to i will not contain the divisors used by the schemes from i-1 to i, because the divisors used by the schemes from i-1 to i will be reduced Pass through the endpoint.
Method of violent finding divisor

#include <iostream>
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1000+5;
const int mod=1000000000+7;
const int maxa=100000+5;
using namespace std;
ll dp[maxn+5];
ll a[maxn+5];
vector<ll>v[maxa+10];
bool book[maxa+5];
ll solve(ll l,ll r){
    ll x=a[r]-a[l];
    ll cnt=0;
    if(x==1){//Note that trees cannot be planted when the distance is 1, and the approximate number 1 cannot be used again, so book[1]=1
        book[1]=1;
        return 0;
    }
    if(book[1]==0){
        book[1]=1;
        cnt++;
        //cout<<1<<"*"<<endl;
    }
    for(ll i=2;i*i<=x;i++){
        if(x%i==0){
            if(book[i]==0){
                book[i]=1;cnt++;
            }
            if(book[x/i]==0){
                book[x/i]=1;cnt++;
            }
        }
    }
    book[x]=1;//Note that x cannot be used before j-1
    return cnt;
}
int main()
{
    int N;
    cin>>N;
    for(int i=0;i<N;i++){
        scanf("%lld",&a[i]);
    }
    dp[0]=1;
    for(ll i=1;i<N;i++){
        memset(book,0,sizeof book);
        for(ll j=i-1;j>=0;j--){
            dp[i]=(dp[i]+dp[j]*solve(j,i))%mod;
        }
    }
    cout<<dp[N-1]<<endl;
    return 0;
}

Making table and finding divisor

#include <iostream>
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1000+5;
const int mod=1000000000+7;
const int maxa=100000+5;
using namespace std;
ll dp[maxn+5];
ll a[maxn+5];
vector<ll>v[maxa+10];
bool book[maxa+5];
int main()
{
    for(int i=1;i<maxa;i++){//For all multiples of i, i is their divisor
        for(int j=2*i;j<maxa;j+=i){//Starting from double, you can rule out the situation of about yourself, because you can't plant trees where there are obstacles
            v[j].push_back(i);
        }
    }
    int N;
    cin>>N;
    for(int i=0;i<N;i++){
        scanf("%lld",&a[i]);
    }
    dp[0]=1;
    for(ll i=1;i<N;i++){
        memset(book,0,sizeof book);//Each partition operation of dp[i-1] has no effect on the partition operation of dp[i], and the tag array should be initialized
        for(ll j=i-1;j>=0;j--){
           ll x=a[i]-a[j];
           ll cnt=0;
           for(int i=0;i<v[x].size();i++){
                if(book[v[x][i]]==0){//Trees cannot be planted on obstacles. For the j-1 point a[j-1], the multiple of the divisor of a[i]-a[j] is the endpoint,
                    book[v[x][i]]=1;//The endpoint is an obstacle, so the divisor before j-1 cannot be reused
                    cnt++;
                }
           }
           book[x]=1;//In particular, although the j-th endpoint cannot be cnt + +, trees cannot be planted at the endpoint. It affects the j-1 endpoint so that it cannot use the divisor a[i]-a[j]
           dp[i]=(dp[i]+dp[j]*cnt)%mod;
        }
    }
    cout<<dp[N-1]<<endl;
    return 0;
}

To try the search, first explode the space in the stack, and then change the set timeout. Note that the global book cannot be opened at this time, because the calculation of each state will be carried out alternately, rather than calculating one after another, so the global book will be disordered.

#include <iostream>
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1000+5;
const int mod=1000000000+7;
const int maxa=100000+5;
using namespace std;
ll dp[maxn+5];
ll a[maxn+5];
vector<ll>v[maxa+10];

ll N;
ll dfs(ll level){
    if(level>=N-1){
        return 1;
    }
//    bool book[maxa+5];
//    memset(book,0,sizeof book);//!!!!
    set<ll>book;
    for(ll i=level+1;i<N;i++){
        if(dp[i]==0){
            dp[i]=dfs(i);
        }
        ll cnt=0,x=a[i]-a[level];
        for(ll j=0;j<v[x].size();j++){
            if(find(book.begin(),book.end(),v[x][j])==book.end()){
                book.insert(v[x][j]);
                cnt++;
            }
        }
        book.insert(x);
        dp[level]=(dp[level]+dp[i]*cnt)%mod;
     //   cout<<"$"<<dp[level]<<" "<<dp[i]<<" "<<cnt<<endl;
    }
    return dp[level];
}
int main()
{
    for(int i=1;i<maxa;i++){//For all multiples of i, i is their divisor
        for(int j=2*i;j<maxa;j+=i){//Starting from double, you can rule out the situation of about yourself, because you can't plant trees where there are obstacles
            v[j].push_back(i);
        }
    }
    cin>>N;
    for(ll i=0;i<N;i++){
        scanf("%lld",&a[i]);
    }
    dp[0]=dfs(0);
    cout<<dp[0]<<endl;
    return 0;
}