Codeforces Round #523 (Div. 2) C-Multiplicity

You are given an integer array $a_{1}, a_{2}, \dots, a_{n}$ .

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 $b_{1}, b_{2}, \dots, b_{k}$ is called to be good if it is not empty and for every $i$ ( $1 \leq i \leq k$ ) $b_{i}$ is divisible by $i$ .

Find the number of good subsequences in $a$ modulo $10^{9} + 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 $2^{n} - 1$ different subsequences (excluding an empty subsequence).

Input

The first line contains an integer $n$ ( $1 \leq n \leq 100 000$ ) — the length of the array $a$ .

The next line contains integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{6}$ ).

Output

Print exactly one integer — the number of good subsequences taken modulo $10^{9} + 7$ .

Examples

input

Copy

2
1 2

output

Copy

input

Copy

5
2 2 1 22 14

output

Copy

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.

Intention: Give you a sequence of length n and find all the number of subsequences that make all ai%i==0.

Answer: Obviously a topic of dynamic programming, using d[i][j] to represent the subsequence size of length j (j must be a factor of ai) in the ith number of the original sequence. The first dimension can be represented by a reverse-order scrolling array of j. It is worth mentioning that you can use the representative to find all the factors. (Harmonic series [n*调和级数], complexity (nlogn))

Code：


#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
const int Mod=1000000007;
ll dp[maxn];
int  a[maxn];
vector<int> v[maxn];
void init()
{
    for(int i=1;i<=1000000;i++)
    {
        for(int j=i;j<=1000000;j+=i)
        {
            v[j].push_back(i);
        }
    }
}
int main()
{
    init();
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=v[a[i]].size()-1;j>=0;j--)
        {
            int tmp=v[a[i]][j];
            dp[tmp]=(dp[tmp]+dp[tmp-1])%Mod;
        }
    }
    ll ans=0;
    for(int i=1;i<=1000000;i++) ans=(ans+dp[i])%Mod;
    printf("%I64d\n",ans);
    return 0;
}

发表评论 取消回复

发表评论取消回复