链接:http://118.190.20.162/view.page?gpid=T125
思路:DP,选择类题目考虑DP
f[i]定义为前i项中种树的种类数目,f[i]=(f[j]*cnt)(0<=j<i,cnt为[j,i)的种类数),由于题目中不允许把树种在已经存在的位置,对于[j,i),j是已经存在的位置,所以往左遍历的时候,[j',i)中的树不能种在j上,即可以通过一个数组st来标记在[j,i)中满足条件的因子k和b(b=j-i,也是不满足的条件),来防止出现多算了cnt的数目。
思路来自acwing讲解
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=100010,mod=(int)1e9+7;
int a[N],f[N];
bool st[M];
vector<int> ve[M];
int main (){
ios::sync_with_stdio(false);
for(int i=1;i<M;i++)
for(int j=i*2;j<M;j+=i)
ve[j].push_back(i);
int n;
cin>>n;
f[0]=1;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=1;i<n;i++){
memset(st,0,sizeof st);
for(int j=i-1;j>=0;j--){
int b=a[i]-a[j];
int cnt=0;
for(int k:ve[b]){
if(!st[k]){
cnt++;
st[k]=true;
}
}
st[b]=true;//
f[i]=(f[i]+1LL*cnt*f[j]%mod)%mod;
}
}
cout<<f[n-1];
return 0;
}