You are given an integer array a1,a2,…,an.
The array b is called to be a subsequence of a if it is possible to remove some elements from a to get b.
Array b1,b2,…,bk is called to be good if it is not empty and for every i (1≤i≤k) bi is divisible by i.
Find the number of good subsequences in a modulo 109+7.
Two subsequences are considered different if index sets of numbers included in them are different. That is, the values of the elements do not matter in the comparison of subsequences. In particular, the array a has exactly 2n−1 different subsequences (excluding an empty subsequence).
Input
The first line contains an integer n (1≤n≤100000) — the length of the array a.
The next line contains integers a1,a2,…,an (1≤ai≤106).
Output
Print exactly one integer — the number of good subsequences taken modulo 109+7.
Examples
inputCopy
2
1 2
outputCopy
3
inputCopy
5
2 2 1 22 14
outputCopy
13
Note
In the first example, all three non-empty possible subsequences are good: {1}, {1,2}, {2}
In the second example, the possible good subsequences are: {2}, {2,2}, {2,22}, {2,14}, {2}, {2,22}, {2,14}, {1}, {1,22}, {1,14}, {22}, {22,14}, {14}.
Note, that some subsequences are listed more than once, since they occur in the original array multiple times.
题意:
给你一个数组,让你删除一些数使得剩下的这些数第i个数能够整除i,问你有多少种方法。
题解:
一开始也想不到该怎么办,后来慢慢就想到了遍历每个数的每个因子这种方法,dp这东西我就是在所有可能的可行解中找这个状态转移方程,一个一个排除就找到了最后的dp方程。dp[i]表示的是数组长度为i有多少种可能,那么遍历一个数的因子的时候就看看dp[因子-1]有多少种可能就好了,注意要从大到小更新,否则会加上自己的因子。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll dp[1000005];
int a[100005];
vector<int>vec[100005];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
int sq=sqrt(a[i]);
for(int j=1;j<=sq;j++)
{
if(a[i]%j==0)
{
vec[i].push_back(j);
if(j*j!=a[i])
vec[i].push_back(a[i]/j);
}
}
sort(vec[i].begin(),vec[i].end());
}
memset(dp,-1,sizeof(dp));
dp[0]=1;
ll ans=0;
for(int i=1;i<=n;i++)
{
for(int j=vec[i].size()-1;j>=0;j--)
{
int num=vec[i][j];
if(dp[num-1]==-1)
continue;
(ans+=dp[num-1])%=mod;
if(dp[num]==-1)
dp[num]=dp[num-1];
else
(dp[num]+=dp[num-1])%=mod;
}
}
printf("%lld\n",ans);
return 0;
}