链接

[http://codeforces.com/contest/1061/problem/C]

题意

给你一个数组，让你找有多少个子串(并非连续，但相对位置不能换)，满足bi%i==0;

分析

dp，直接先把ai的所有因子抠出来，并从小到大排序（这个很重要），然后dp[i]表示到当前这个数字，子串

长度为i的有多少个，很显然长度为i的依赖于前面的数字长度为i-1的子串数量，所以dp[vec[i][j]]=(dp[vec[i][j]]+dp[vec[i][j]-1])%mod;

为什么从大的因子枚举，因为在一个子串里该数字只能用一次，不然会多出。最后统计并取模,看代码体会吧。

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

vector<ll> vec[100010];

ll a[100010];

ll dp[1000010];

const ll mod=1e9+7;

int main(){

    int n;

    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);

    cin>>n;

    for(int i=0;i<n;i++)

    {

        cin>>a[i];

        for(int j=1;j*j<=a[i];j++){

            if(a[i]%j==0){

                vec[i].pb(j);

                if(j*j!=a[i]) vec[i].pb(a[i]/j);

            }

        }

        sort(vec[i].begin(),vec[i].end());

    }

    dp[0]=1;

    for(int i=0;i<n;i++){

        for(int j=vec[i].size()-1;j>=0;j--)

        {

            dp[vec[i][j]]=(dp[vec[i][j]]+dp[vec[i][j]-1])%mod;

        }

    }

    ll ans=0;

    for(int i=1;i<=n;i++)

    {

       ans=(ans+dp[i])%mod;

       ans%=mod; if(dp[i]==0) break;

    }

    cout<<ans<<endl;

    return 0;

}