题意：给定一个数组{an}，问这个数组的所有子序列{bm}中，有多少子序列满足:对于所有的i(1<=i<=m)满足bi是i的倍数，答案对10^9+7取模

题解：

首先想到二维DP，从i长中找到j长的子序列的方法=dp[i][j]

如果a[i]可以除以j，原式=dp[i-1][j-1]+dp[i-1][j]

否则，原式=dp[i-1][j]；

j可以通过枚举a[i]的因数得到

然后我们发现可以把i这个维度压掉…

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 5;
int a[maxn];
vector<int> v[maxn];
int dp[maxn];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        v[i].clear();
        for (int j = 1; j * j <= a[i]; j++) {
            if (a[i] % j == 0) {
                v[i].push_back(j);
                if (j * j != a[i]) {
                    v[i].push_back(a[i] / j);
                }
            }
        }
        sort (v[i].begin(), v[i].end());
    }
    int ans = 0;
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = v[i].size() - 1; j >= 0; j--) {
            dp[v[i][j]] = (dp[v[i][j]] + dp[v[i][j] - 1]) % mod;
        }
    }
    for (int i = 1; i <= n; i++) {
        ans = (ans + dp[i]) % mod;
    }
    cout << ans<< endl;
    return 0;
}