牛牛与数组
牛牛与数组
http://www.nowcoder.com/questionTerminal/ea8bea245af54de7b918e5d587af4e0c
题解：使用二维数组确定每一个的状态。记录以当前数字结尾满足条件的数组数量。
AC-code
#include
using namespace std;
typedef long long ll;
const int MAXN = 1e5+5;
const ll mod = 1e9+7;
ll dp[12][MAXN]={0};
int main(){
ll N,K;
scanf("%lld%lld",&N,&K);
for(int i=1;i<=K;i++){
dp[1][i]=1;
}
ll sum=K;
for(int i=2;i<=N;i++){
ll res=0;
for(int j=1;j<=K;j++){
dp[i][j]=sum%mod;
for(int k=j*2;k<=K;k+=j){
dp[i][j]=(dp[i][j]-dp[i-1][k]+mod)%mod;
}
res=(res+dp[i][j])%mod;
}
sum=res;
}
printf("%lld\n",sum);
return 0;
}