第22次CCF计算机软件能力认证 第四题 校门外的树（dp）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1010,M=1e5+10,mod=1e9+7;
vector<int>v[M];
bool st[M];
int f[N],n,a[N];

signed main(){
    for(int i=1;i<M;i++){
        for(int j=2*i;j<M;j+=i){
            v[j].push_back(i);
        }
    }
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    f[1]=1;
    for(int i=2;i<=n;i++){
        memset(st,0,sizeof st);
        for(int j=i-1;j>=1;j--){
            int d=a[i]-a[j],cnt=0;
            for(int k:v[d]){
                if(!st[k]){
                    cnt++;
                    st[k]=1;
                }
            }
            st[d]=1;
            f[i]=(f[i]+f[j]%mod*cnt%mod)%mod;
        }
        
    }
    cout<<f[n]<<endl;
}