牛牛与数组（简单dp+优化）

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

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld

题目描述

牛牛喜欢这样的数组： 1：长度为n 2：每一个数都在1到k之间 3：对于任意连续的两个数A，B，A<=B 与（A % B != 0） 两个条件至少成立一个 请问一共有多少满足条件的数组，对1e9+7取模

输入描述:

输入两个整数n,k 1 ≤ n ≤ 10 1 ≤ k ≤ 100000

输出描述:

输出一个整数

示例1

输入

复制

2 2

输出

复制

3

示例2

输入

复制

9 1

输出

复制

1

示例3

输入

复制

3 3

输出

复制

15

示例4

输入

复制

2 1234

输出

复制

1515011

 dp[i][j]表示第i位放j的方案数，转移方程为dp[i][j]=dp[i-1][k]{k<=j||k%j!=0}

直接暴力枚举直接就TLE了，但是可以写出来看看能不能优化，很明显一个简单的优化就可以了

时间复杂度n*[(k/1+k/2+……k/k)-k],后面这个式子可以分块算，也可以用微积分原理来算

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; ll dp[12][100005]; int main(){ int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=k;i++) { dp[1][i]=1; } // for(int i=2;i<=n;i++){ // for(int A=1;A<=k;A++){ // for(int B=1;B<=k;B++){ // if((A<=B)||(A%B!=0)) { // dp[i][B]+=dp[i-1][A]; // dp[i][B]%=mod; // } // } // } // } ll sum1=k; ll sum2=0; for(int i=2;i<=n;i++){ for(int B=1;B<=k;B++){ dp[i][B]=sum1; int up=k/B; for(int j=2;j<=up;j++){ dp[i][B]-=dp[i-1][j*B]; } dp[i][B]=(dp[i][B]%mod+mod)%mod; sum2+=dp[i][B]; } sum1=sum2; sum2=0; } ll ans=0; for(int i=1;i<=k;i++){ ans=(ans+dp[n][i])%mod; } printf("%lld\n",ans); return 0; }