题解 | #牛牛与数组#

n,k=map(int,input().split())
mod=10**9+7
f=[0]+[1]*k

for _ in range(n-1):
    total=sum(f)%mod
    nf=[0]*(k+1)
    for i in range(1,k+1):
        if i==1:
            nf[i]=1
        else:
            nf[i]=total
            for c in range(2,k+1):
                if c*i>k:
                    break
                nf[i]=(nf[i]-f[c*i]+mod)%mod
    f=nf
print(sum(f)%mod)

每一个数前面可以放什么数？要么是小于等于他的数，要么是大于他且不是他的倍数

所以我们先加前一行的总和，然后再去减前一行里是这个数倍数的项

会不会超时呢，写一个暴力的程序在本地跑了一遍就很容易得到，[2,1e5)这个区间里面每个数的倍数个数总和为966751，而n最大为10，相乘也不会超过1e7，所以轻轻松松搞定