链接：https://ac.nowcoder.com/acm/problem/21738
来源：牛客网

题目描述
牛牛喜欢这样的数组：
1：长度为n
2：每一个数都在1到k之间
3：对于任意连续的两个数A，B，A<=B 与（A % B != 0） 两个条件至少成立一个

请问一共有多少满足条件的数组，对1e9+7取模
输入描述:
输入两个整数n,k

1 ≤ n ≤ 10
1 ≤ k ≤ 100000
输出描述:

输出一个整数

题目分析：动态规划问题，第一步设状态，第二步初始值，第三步状态转移，第四步确定答案。
1.状态：f[i][j]表示在前i个数中，第i个数选j能当前满足条件的数列。
2.初始值：f[1][i]=1 (1<=i<=k)
3.状态转移方程：f[i][j]=(sum(f[i-1][x])+sum(f[i-1][y]))%M (1<=x<=j,j+1<=y<=k&&y%j!=0)
4.Ans=sum(f[n][i]) (1<=i<=k)
时间复杂度：O(n*k^2)
但是，k<=100000
很明显，会超时
因此，必须优化

观察状态转移方程可以发现，1到j和j+1到k刚好k次，且都是连续相加求和，
所以设s1,s2数组分别表示f[i-1][j]前缀和和后缀和。
状态转移方程为：f[i][j]=sum(s1[j]+s2[j])%M-f[i-1][x] (x%j==0)
Ans=sum(f[n][i])

代码如下：

#include<bits/stdc++.h>
#define M 1000000007
using namespace std;
int n,k;
long long ans,f[12][100002],s1[100002],s2[100002];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=k;i++)f[1][i]=1;
    for(int i=2;i<=n;i++)
    {
        memset(s1,0,sizeof(s1));
        memset(s2,0,sizeof(s2));
        for(int j=1;j<=k;j++)s1[j]=(s1[j-1]+f[i-1][j])%M;
        for(int j=k;j>=1;j--)s2[j]=(s2[j+1]+f[i-1][j])%M;
        for(int j=1;j<=k;j++)
        {
            f[i][j]=(s1[j]+s2[j])%M;
            for(int x=j;x<=k;x+=j)f[i][j]=(f[i][j]+M-f[i-1][x])%M;
//          for(int x=1;x<=j;x++)
//            f[i][j]+=f[i-1][x];
//          if(f[i][j]>=1e15)f[i][j]%=M;
//          for(int x=j+1;x<=k;x++)
//            if(x%j!=0)f[i][j]+=f[i-1][j];
//          if(f[i][j]>=1e15)f[i][j]%=M;
        }
    }
     
    for(int i=1;i<=k;i++)
      ans=(ans+f[n][i])%M;
    cout<<ans%M;
    return 0;
}
欢迎大家讨论，谢谢！