Submission #6171699

---

Source Code Expand

import numpy as np
N,K = map(int,input().split())
MOD = 10 ** 9 + 7
M = int(N**.5)

# M+1以上で、商がぢょうとxになるやつ
upper_cnt = np.zeros(M+1, dtype=np.int64)
a = np.arange(M+1, dtype=np.int64)
upper_cnt[1:] = N // a[1:] - np.maximum(M, N // (a[1:]+1))

# 数列の末端ごとの個数
# upperについては、個数にわたって合計をとる
dp_lower = np.zeros((K+1,M+1), dtype=np.int64)
dp_upper = np.zeros((K+1,M+1), dtype=np.int64)
# 0項目に1を置いておくとする
dp_lower[0,1] = 1
for k in range(1,K+1):
    prev_lower = dp_lower[k-1]
    prev_upper = dp_upper[k-1]
    cum_lower = prev_lower.cumsum() % MOD
    cum_upper = prev_upper.cumsum() % MOD
    # 下側 to 下側
    dp_lower[k] += cum_lower[-1]
    # 上側 to 下側
    dp_lower[k] += cum_upper[-1]
    dp_lower[k,1:] -= cum_upper[:-1] # 商がn-1以下だと受け付けない
    dp_lower[k,0] = 0
    # 上側 to 上側：ないはず
    # 下側 to 上側：
    dp_upper[k] = cum_lower * upper_cnt
    dp_lower %= MOD
    dp_upper %= MOD
    
answer = (dp_lower[K].sum() + dp_upper[K].sum()) % MOD
print(answer)

Submission Info

Judge Result