Codeforces Contest 1061 problem C . Multiplicity——DP

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;
}