C. Multiplicity (CF 523 Div.2)
https://mp.csdn.net/postedit/84366147
简单dp题，公式是很好推的就是暴力超时呀，其实每次找的都是第i个数的不超过i的因子x，dp的s数组统计的是左边到当前位置长度为x的个数，所以当前位置截至的长度为x的个数就是左面长度为x-1的个数，这个很好推，那么对于第i个数，就不要直接O（a[i]）的循环了，用O（sqrt(a[i])），找因子，然后因为是跟左面的有关，x-1对应的个数不能是当前位置更新过的，所以只需要用两个数记录一下就可以。
代码：
#include
using namespace std;
#define mod 1000000007
long long n,m,a[100005],ans,s[100005],t,l,ll;
int main()
{t=-11;scanf("%I64d",&n);s[0]=1;for(int i=1;i<=n;i++){scanf("%I64d",&a[i]);m=min((int)sqrt(a[i]),i);for(int j=1;j<=m;j++){if(a[i]%j==0){if(a[i]/j<=i&&(a[i]/j)!=j){s[a[i]/j]+=s[(a[i]/j)-1];s[a[i]/j]%=mod;//cout<<(i&1)<<" !!!! "<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！