Lisa

先想一个朴素的 dp

$f_{i,j}$表示前 $i$ 个把 $i$ 放在子序列 $j$ 位的方案数，显然我们的 $j$ 不是 $a_i$的因数的时候

会直接从上一位继承下来

是不是有 背包那味了

对于每一个 $a_i$ 我们分解质因子再转移

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#define int long long
using namespace std;
int n;
int a[2000001];
int cnt1,cnt2;
int s[2000001],ss[2000001];
int f[2000001];
int mod=1000000007;
signed main(){
    scanf("%lld",&n);
    f[0]=1;
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        int lim=sqrt(a[i]);
        cnt1=cnt2=0;
        for(int j=1;j<=lim;++j){
            if(a[i]%j==0){
                s[++cnt1]=j;
            if(j*j!=a[i]){
                ss[++cnt2]=a[i]/j;
                }
            }
        }
        for(int j=1;j<=cnt2;++j){
            f[ss[j]]=f[ss[j]]+f[ss[j]-1];
            f[ss[j]]%=mod;
        }
        for(int j=cnt1;j>=1;--j){
            f[s[j]]=f[s[j]]+f[s[j]-1];
            f[s[j]]%=mod;
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        ans=(ans+f[i])%mod;
    }
    cout<<ans;
    return 0;
}