题目传送门CF1061C
洛谷入口
题目大意
(有个长度为n的序列a，你需要统计a中有多少个棒棒的子序列)
(一个序列b被定义为棒棒的，当且仅当：)
(对于序列中每一个位置i，b_i都能够被i整除)
(答案对10^9+7 取模)
数据范围
(circ) (nle10^5)
(circ) (1le a_ile10^6)
题解
这题可能是最近几道题里最简单的一道了
不难想到暴力做法：
(dp_{i,j}指枚举到i点，b序列长度为j的方案个数)
(则状态转移方程是：)
(dp_{i,j}=dp_{i-1,j}+(a_i)%(j==0) imes dp_{i-1,j-1})
这样暴力的复杂度是(O(n^2))的，会超时
于是考虑一下优化
试着维护一下二维前缀和
然后可以新添的长度(j要求是a_i)的因数
于是可以试着枚举(a_i)的所有因数
DP一下这个a[i]对所有因数（就是可能长度）的贡献（好吧本人蒟蒻难以准确说明，具体见代码吧）
复杂度是根号级别的
所以总复杂度就会是(O(nsqrt n))的了
因为(n是10^5)的，于是可以3秒跑过了
具体实现看下面代码↓↓↓
AC代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,ans,mod=1e9+7;
ll a[1000010],f[1000010];//用于dp的f[i]表示目前为止长度为i的合法序列个数
ll w[1000010];//存放a[i]的每一个因数
int main(){
cin>>n;
for(ll i=1;i<=n;++i)cin>>a[i];
f[0]=1;//为了使f能够合乎常理（？）地DP
for(ll i=1;i<=n;++i){
ll qq=sqrt(a[i]),top=0;
for(ll j=1;j<=qq;j++){
if(a[i]%j==0){
w[++top]=j;
if(j*j!=a[i])//这句缺失会导致错误，如1,1,2->5就WA了
w[++top]=a[i]/j;
}
}
sort(w+1,w+top+1);
for(ll j=top;j>=1;--j){
f[w[j]]=(f[w[j]]+f[w[j]-1])%mod;
}
}
for(ll i=1;i<=n;++i)ans=(ans+f[i])%mod;
cout<<ans;
}