题意

定义动态规划数组 $dp[n][n]$，其中 $dp[i][j]$ 表示从前 $i$ 个元素 $a_1, a_2, \dots, a_i$ 中选出大小为 $j$ 的“好子序列”的方案数。最终答案为 $\sum_{i=1}^{n} dp[n][i]$。

思路

状态转移方程为：

$$dp[i][j] = \begin{cases} dp[i-1][j] + dp[i-1][j-1] & \text{如果 } a[i] \text{ 是 } j \text{ 的倍数} \\ dp[i-1][j] & \text{否则} \end{cases} $$

直接维护二维 $dp$ 会超出内存限制，但注意到 $dp[i]$ 只依赖于 $dp[i-1]$，因此可以用一维 $dp$ 数组滚动更新。此外，$dp[j]$ 只有在 $j$ 是 $a[i]$ 的约数时才需要更新。我们可以用 $O(\sqrt{x})$ 的时间求出数 $x$ 的所有约数。

算法步骤

1. 初始化一维数组 $dp$，长度为 $n+1$，$dp[0] = 1$，其余为 $0$。
2. 遍历每个元素 $a[i]$：
   • 求出 $a[i]$ 的所有约数。
   • 对于每个约数 $d$（从大到小遍历，避免重复更新），执行 $dp[d] = dp[d] + dp[d-1]$。
3. 最终答案为 $\sum_{j=1}^{n} dp[j]$。

复杂度分析

• 时间复杂度：$O(n \cdot (\text{maxD} + \sqrt{\text{maxA}}))$，其中 $\text{maxD}$ 表示最大约数个数，$\text{maxA}$ 表示 $a_i$ 的最大值。
• 也可以使用筛法预处理每个数的约数，时间复杂度为 $O(\text{maxA} \cdot \log(\text{maxA}) + n \cdot \text{maxD})$。

代码说明

• 使用一维数组 $dp$ 滚动更新，节省空间。
• 对于每个 $a[i]$，枚举其所有约数，并按照从大到小的顺序更新 $dp$，确保每个 $j$ 只被当前元素更新一次。
• 最终累加 $dp[1]$ 到 $dp[n]$ 得到答案。

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
long long n,a[1000010],f[1000010],ans,y[1000010];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    f[0]=1;//使单独一个数能成为合法子序列
    for(int i=1;i<=n;i++){
    	int top=0;
    	for(int j=1;j<=sqrt(a[i]);j++){
    		if(a[i]%j)continue;
			y[++top]=j;
			if(j*j!=a[i])y[++top]=a[i]/j;
		}//求因数 
		sort(y+1,y+top+1);//排序 
    	for(int j=top;j>=1;j--)
    		f[y[j]]=(f[y[j]]+f[y[j]-1])%mod;//状态转移方程 
	}
	for(int i=1;i<=n;i++)
		ans=(ans+f[i])%mod;
	cout<<ans;
    return 0;
}