Problem:


Score : 600 points

Problem Statement

Find the number of sequences of length K consisting of positive integers such that the product of any two adjacent elements is at most N, modulo 10^9+7.

Constraints

1\leq N\leq 10^9

1 2\leq K\leq 100 (fixed at 21:33 JST)

N and K are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the number of sequences, modulo 10^9+7.

Sample Input 1

3 2

Sample Output 1

5

(1,1), (1,2), (1,3), (2,1), and (3,1) satisfy the condition.

Sample Input 2

10 3

Sample Output 2

147

Sample Input 3

314159265 35

Sample Output 3

457397712



Sample input:
3 2


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
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 status: Accepted

Solution code:
from collections import *
import sys
try: fin = open('in')
except: fin = sys.stdin
input = lambda: fin.readline().strip()

mod = 10 ** 9 + 7

n, k = map(int, input().split())
nparts = []
i = 1
while i <= n:
	j = n // (n // i)
	nparts.append(j - i + 1)
	i = j + 1

row = nparts
for r in range(1, k):
    tmp = []
    s = 0
    for i in range(len(nparts) - 1, -1, -1): # go backwards
        s += row[-(i + 1)] # prefix sum thingy
        tmp.append(s * nparts[i] % mod)
    tmp.reverse()
    row = tmp

print (sum(row) % mod)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
L = 10**9+7

parts = []
i = 1
while i<=N:
    a = N // i
    j = N // a
    parts.append(j-i+1)
    i = j+1

C = parts
for _ in range(K-1):
    C_new = []
    c = 0
    for i,p in enumerate(parts[::-1]):
        num_dual = i
        c += C[i]
        C_new.append(p * c % L)
    C = C_new[::-1]
print(sum(C) % L)

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def sqrt_case_manager(N):
    # x ∈ [1, N] に対して、N//x の取りうる値と、その値を取るときの x の範囲（半開区間）を列挙
    # O(sqrt(N))
    l = 1
    while l <= N:
        r = N//(N//l) + 1
        yield N//l, l, r
        l = r

def solve(N, K, cases):
    # dp[k][n] := k 個目まで見て、k 個目に n を置く場合の数
    #           = sum( dp[k-1][N/n以下] )
    # dp[k][l,r] := k 個目まで見て、k 個目に [l, r) を置く場合の数
    #              ただし n' ∈ [l, r) について N/n' は同じ値を取る
    #             = sum( dp[k-1][N/l以下] )
    mod = 10**9+7
    dp = np.zeros((K+1, len(cases)), dtype=np.int64)
    dp[0, 0] = 1
    for k in range(1, K+1):
        cum = 0
        for n in range(len(cases)):
            cum = (cum + dp[k-1, n]) % mod
            _, l, r = cases[-n-1]
            dp[k, -n-1] = cum * (r-l) % mod
    print(dp[-1].sum() % mod)


numba_compile([
    [solve, "(i8,i8,i8[:,:])"],
])


def main():
    N, K = map(int, input().split())
    cases = np.array(list(sqrt_case_manager(N)), dtype=np.int64)
    solve(N, K, cases)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math
import copy
N, K = map(int, input().split())

mod = 10**9+7

if N == 1:
    ans = 1
else:
    Keys = set()
    for n in range(1, int(math.sqrt(N))+2):
        Keys.add(n)
        Keys.add(N//n)

    L = sorted(list(Keys))
    Counts = {1: 1}
    for i in range(len(L)-1):
        Counts[L[i+1]] = L[i+1]-L[i]

    dp = copy.copy(Counts)
    for _ in range(K-1):
        sdp = {}
        c = 0
        for l in L:
            c = (c + dp[l]) % mod
            sdp[l] = c

        for l in L:
            r = N//l
            dp[l] = sdp[r] * Counts[l] % mod

    ans = 0
    for v in dp.values():
        ans = (ans + v) % mod
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s = set()
i = 1

while i*i<=N:
    s.add(i)
    s.add(N//i)
    i += 1

l = list(s)
l.sort()
nums = []

for i in range(len(l)-1):
    le = N//l[i+1]
    ri = N//l[i]
    nums.append(ri-le)

nums.append(1)
nums.reverse()
M = len(nums)
dp = [[0]*M for _ in range(K+1)]
dp[0][0] = 1
MOD = 10**9+7

for i in range(K):
    acc = [0]
    
    for j in range(M):
        acc.append((acc[-1]+dp[i][j])%MOD)
    
    for j in range(M):
        dp[i+1][j] = nums[j]*acc[M-j]

print(sum(dp[K])%MOD)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,K = MI()
mod = 10**9+7

B = [i for i in range(int(N**.5)+1)]
C = [N//i for i in range(1,int(N**.5)+1)]
C.reverse()

if B[-1] == C[0]:
    del C[0]

D = B+C
A = [D[i+1]-D[i] for i in range(len(D)-1)]
a = len(A)
dp = [[0]*a for _ in range(K)]
for i in range(K):
    if i == 0:
        for j in range(a):
            if j == 0:
                dp[i][j] = A[j]
            else:
                dp[i][j] = dp[i][j-1] + A[j]
                dp[i][j] %= mod
    else:
        for j in range(a):
            if j == 0:
                dp[i][j] = dp[i-1][a-j-1]
            else:
                dp[i][j] = dp[i][j-1] + dp[i-1][a-j-1]*A[j]
                dp[i][j] %= mod

print(dp[-1][-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
MOD = 10 ** 9 + 7


dist = [(n + 1, n + 1)]
r = n + 1
for i in range(2, n + 100):
    # [l, r)
    r = dist[-1][0]
    l = n // i + 1
    if r - l < 1:
        break
    dist.append((l, r))

while True:
    if r == 1:
        break
    dist.append((r - 1, r))
    r -= 1

dist = dist[::-1]
del dist[-1]


length = [r - l for l, r in dist]
dp = [[0] * len(dist) for i in range(k)]
for i in range(len(dist)):
    dp[0][i] = length[i]

for i in range(k - 1):
    ru = 0
    for j in range(len(dist)):
        ru += dp[i][j]
        ru %= MOD
        dp[i + 1][~j] += ru * length[~j]
        dp[i + 1][~j] %= MOD

print(sum(dp[-1]) % MOD)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 1000000007
a = []

i = 1
while i * i <= n:
    a.append(i)
    a.append(n // i)
    i += 1
m = len(a)
a.append(0)
a.sort()

dp = [0] * m
dp[0] = 1
acc = [0]  * m
for _ in range(k):
    acc[0] = dp[0]
    for j in range(1, m):
        acc[j] = (acc[j-1] + dp[j]) % mod # 累積和
    for j in range(m):
        dp[j] = acc[m-j-1] * (a[j+1] - a[j]) % mod
ans = 0
for x in dp:
    ans = (ans + x) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    """
    末尾だけが重要，dp[i][j]でi枚目まで見て末尾がj，O(NK)
    Nが小さければ問題ない，jの部分は(N/j)の切り捨てでまとめられる．
    前半部分は1~sqrt(N)で，各組1こずつ．後半はN/i (i<=sqrt(N))
    
    """
    N,K=MI()
    M=int(N**0.5)
    cnt=[]
    
    i=1
    while i<=N:
        if i<=M:
            cnt.append(1)
            i+=1
        else:
            temp=int(N/i)
            cnt.append(int(N/temp-i+1))
            i=int(N/temp +1)
            
    N2=len(cnt)
            

    
    dp=[[0]*N2 for _ in range(K)]
    #dp[i][j]はi個見て，最後尾がグループL[j]に属す場合の数
    #j番目のグループはMーj番目までのグループと組める
    
    for j in range(N2):
        dp[0][j]=cnt[j]
        
    for i in range(K-1):
        S=[0]*(N2+1)
        for j in range(N2):
            S[j+1]=(S[j]+dp[i][j])%mod
        
        for j in range(N2):
            dp[i+1][j]=(S[N2-j]*cnt[j])%mod
            
    ans=0
    for j in range(N2):
        ans=(ans+dp[-1][j])%mod
        
    print(ans)


    
    

main()

Submission status: Accepted

Solution code:
def calc_floors(N):
    # floor(N / n) (n = 1, ..., N) のとりうる値と
    # 各floorの値を与えるnの範囲（閉区間）を返す
    n_values = list()
    n_ranges = list()
    k = 1
    while k <= N:
        # k = floor(N / n)  <-->  N/(k+1) < n <= N/k
        # N/(k+1)より大きい最小の整数は(N + k + 1) // (k + 1)
        left, right = (N + k + 1) // (k + 1), N // k
        n_values.append(k)
        n_ranges.append((left, right))
        if left == 1:
            break
        k = N // (left - 1)
    return n_values, n_ranges


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split()))
    n_values, n_ranges = calc_floors(N)
    # dp[k][i]: k個目までで題意を満たす＆一番右の数が区分iの範囲に入るような整数の組の個数
    dp = [[0 for _ in range(len(n_values))] for _ in range(K)]
    dp[0][0] = n_values[0]
    for i in range(1, len(n_values)):
        dp[0][i] = n_values[i] - n_values[i - 1]
    dp[0].reverse()
    for k in range(1, K):
        # dpの累積和（後ろから順に）
        csdp = [0 for _ in range(len(n_values))]
        csdp[len(n_values) - 1] = dp[k - 1][len(n_values) - 1]
        for i in range(len(n_values) - 2, -1, -1):
            csdp[i] = csdp[i + 1] + dp[k - 1][i]
        # dpの更新
        for i in range(len(n_values)):
            v = csdp[len(n_values) - i - 1] * (n_ranges[i][1] - n_ranges[i][0] + 1)
            dp[k][i] = v % MOD
    ans = 0
    for i in range(len(n_values)):
        ans += dp[K - 1][i]
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    mod = 7 + 10 ** 9
    S = 1
    while S ** 2 <= N:
        S += 1
    DP = [[[0, 0] for _ in range(S)] for _ in range(K)]
    Rev = [0] * S
    S -= 1
    Rev[S] = (N // S - S) % mod
    for i in reversed(range(1, S)):
        Rev[i] = ((N // i) - (N // (i + 1))) % mod
    for i in range(1, S + 1):
        DP[0][i][0] = 1
        DP[0][i][1] = Rev[i]
    for i in range(2, S + 1):
        DP[0][i][0] += DP[0][i-1][0]
        DP[0][i][0] %= mod
    DP[0][S][1] += DP[0][S][0]
    DP[0][S][1] %= mod
    for i in reversed(range(1, S)):
        DP[0][i][1] += DP[0][i+1][1]
        DP[0][i][1] %= mod

    for i in range(1, K):
        for j in range(1, S + 1):
            DP[i][j][0] += DP[i-1][j][1]
            DP[i][j][1] += (DP[i-1][j][0] * Rev[j]) % mod
            DP[i][j][1] %= mod
            DP[i][j][0] += DP[i][j-1][0]
            DP[i][j][0] %= mod
        DP[i][S][1] += DP[i][S][0]
        DP[i][S][1] %= mod
        for j in reversed(range(1, S)):
            DP[i][j][1] += DP[i][j+1][1]
            DP[i][j][1] %= mod

    print(DP[K-1][1][1])
    #print(DP)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math

mod = 10**9+7
N, K = map(int, input().split())
K -= 1

P = set()
inv = {}
for i in range(1, int(math.sqrt(N)+2)):
    if i**2 > N: break
    P.add(i)
    P.add(N//i)
    if i not in inv:
        inv[i] = N//i
    if N//i not in inv:
        inv[N//i] = i

P1 = sorted(list(P))

T = len(P1)

M = [1]
for i in range(T-1):
    M.append(P1[i+1]-P1[i])


co_to_ind = {}
for i, p in enumerate(P1):
    co_to_ind[p] = i

Inv = []
for p in P1:
    Inv.append(co_to_ind[inv[p]])

dp = [[0]*T for _ in range(K+1)]

dp[0] = M

for i in range(K):
    tosum = [0]*T
    for ik in range(T):
        j = Inv[ik]
        tosum[j] = (tosum[j] + dp[i][ik]) % mod

    sumup = 0
    for ik in reversed(range(T)):
        sumup = (sumup + tosum[ik]) % mod
        dp[i+1][ik] = sumup * M[ik] % mod

ans = 0
for t in range(T):
    ans = (ans + dp[K][t]) % mod

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n,k=map(int,input().split())
if n==1:exit(print(1))
d=[1]
t=[1]
for i in range(2,int(n**0.5)+2):
  if n//d[-1]!=n//i:
    d.append(i)
    t.append(1)
  else:
    t[-1]+=1
dd=[]
for i in range(d[-1],0,-1):
  if n//i<=d[-1]:continue
  dd.append(n//i)
x=d+dd
for i in range(len(t),len(x)):
  t.append(x[i]-x[i-1])
di=[0]*len(x)
mod=10**9+7
for i in range(len(x)):di[i]=bisect_left(x,n//x[i])
n=len(x)
dp=[n*[0]for _ in range(k)]
dp[0]=t[:]
for i in range(1,k):
  for j in range(1,n):
    dp[i-1][j]+=dp[i-1][j-1]
    dp[i-1][j]%=mod
  for j in range(n):dp[i][j]=dp[i-1][di[j]]*t[j]%mod
print(sum(dp[-1])%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    l=1
    from collections import defaultdict
    dp=dict()
    ndp=dict()
    for i in range(K):
        ndp=dict()
        l=N
        s=0
        while l>0:
            d=N//l
            r=N//(d+1)
            if i==0:
                s=1
            else:
                s+=dp[d]
            ndp[l]=(l-r)*s%mod
            l=r
        dp=ndp
    ans=0
    from functools import reduce
    ans=reduce(lambda a,b:(a+b)%mod, dp.values())
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    l=1
    from collections import defaultdict
    dp=dict()
    ndp=defaultdict
    for i in range(K):
        ndp=dict()
        l=N
        s=0
        while l>0:
            d=N//l
            r=N//(d+1)
            if i==0:
                s=1
            else:
                s+=dp[d]
            ndp[l]=(l-r)*s%mod
            l=r
        dp=ndp
    ans=0
    for v in dp.values():
        ans=ans+v
        ans%=mod 
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
MOD = 10**9+7
  
n, k = map(int, input().split())
S = set()
i = 1
while i * i <= n:
  S.add(i)
  S.add(n//i)
  i += 1
L = np.array([0] + sorted(S), dtype=np.int64)
l = len(L) - 1
num = np.diff(L)
dp = np.zeros(l, dtype=np.int64)
dp[0] = 1
for _ in range(k):
  A = np.cumsum(dp)
  dp = A[::-1] * num
  dp %= MOD
ans = dp.sum() % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10**9+7

def main():
  n, k = map(int, input().split())
  S = set()
  i = 1
  while i * i <= n:
    S.add(i)
    S.add(n//i)
    i += 1
  L = [0] + sorted(S)
  l = len(L) - 1
  num = [0]*l
  for i in range(l):
    num[i] = L[i+1] - L[i]
  dp = [0]*l
  dp[0] = 1
  for _ in range(k):
    A = list(accumulate(dp))
    for i in range(l):
      dp[i] = A[l-1-i] * num[i]
      dp[i] %= MOD
  ans = sum(dp) % MOD
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
# Nが100以下の時は全部れっきょ

import math
N, K = map(int, input().split())
mod = 10**9+7


def rev(X):
    return pow(X, mod-2, mod)


if N <= 100:
    dp = [[0 for i in range(N+2)] for i in range(K+1)]
    for i in range(1, N+1):
        dp[1][i] += 1
    for i in range(2, K+1):
        for j in range(1, N+1):
            dp[i][1] += dp[i-1][j]
            dp[i][N//j+1] -= dp[i-1][j]
        for j in range(1, N+2):
            dp[i][j] += dp[i][j-1]
    ans = 0
    for i in range(1, N+1):
        ans += dp[K][i]
    print(ans % mod)
    exit()


else:
    # N>100
    ans = 0
    L=0
    for i in range(10**5):
        if i**2>N:
            L=i  
            break
    B = N//L
    dp = [[0 for i in range(L+B)] for i in range(K+1)]
    cnt = [0 for i in range(L+B)]
    for i in range(1, B+1):
        dp[1][i] += 1
        cnt[i] = 1
    for i in range(B+1, B+L):
        x = B+L-i
        dp[1][i] += N//x-N//(x+1)
        cnt[i] = N//x-N//(x+1)
    for i in range(2, K+1):
        S = sum(dp[i-1])
        for j in range(1, L+B-1):
            dp[i][j] = S*cnt[j] % mod
            S -= dp[i-1][-j]
        dp[i][L+B-1] = S*cnt[L+B-1] % mod
    for i in range(1, L+B):
        ans += dp[K][i]
        ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
coef=[]
for i in range(1,int(n**0.5)+1):
  coef.append((n//i)-(n//(i+1)))
coef+=[1]*(n-sum(coef))
coef=coef[::-1]
nn=len(coef)
dp=[[0]*nn for _ in range(k+1)]
dp[0][0]=1
for i in range(1,k+1):
  tmp=0
  for j in range(nn-1,-1,-1):
    tmp+=dp[i-1][(nn-1)-j]
    tmp%=mod
    dp[i][j]=coef[j]*tmp
    dp[i][j]%=mod
print(sum(dp[k])%mod)

Submission status: Accepted

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    N, K = LI()
    n = int(N**0.5)
    C = [] # N//j=indexとなるjの個数
    L = [0]*(2*int(n)) # N//indexの解 =>要りません。。
    for i in range(1,n+1):
        now = N//i - N//(i+1)
        C.append(now)
    for i in range(1,n+1):
        if N//i==i:
            continue
        C.append(1)
    C.reverse()
    #print(C)
    n = len(C)
    #for i in range(1,n+1):
    #    L[i-1] = N//i
    #for i in range(n):
    #    L[i+n] = n - i
    #L.reverse()
    #print(L)
    dp = [[0]*(n) for _ in range(K)]

    for i in range(n):
        dp[0][i] = C[i]
    #print(dp[0])
    for i in range(K-1):
        S = 0
        for j in range(n):
            S += dp[i][j]
            S %= mod
            dp[i+1][n-j-1] = S*C[n-j-1] %mod
    #print(dp)
    ans = 0
    for s in dp[-1]:
        ans += s
        ans %= mod
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
mod = 10**9+7

s = set()
for i in range(1,int(n**0.5)+1):
    s.add(i)
    s.add(n//i)
l = sorted(list(s))
d = {}
x = len(l)
for i in range(x-1):
    le = n//l[i+1]
    ri = n//l[i]
    d[l[i]] = [ri-le,i]
d[l[-1]] = [1,x-1]

dp = [[0]*(x) for i in range(k+1)]
dp[0][0] = 1
for i in range(k):
    for j in range(x-1):
        dp[i][j+1] += dp[i][j]
        dp[i][j+1] %= mod
    
    for j in range(x):
        s,nj = d[n//l[j]]
        dp[i+1][j] += dp[i][nj]*s
        dp[i+1][j] %= mod
    
print(sum(dp[-1])%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 桁dp、√Nまでをlower、それ以降をup_range、Nをlowerで割ったものでまとめる
MOD = 10 ** 9 + 7
N, K = lr()
M = int(N ** .5)
A = np.arange(M+1, dtype=np.int64)
high_range = np.zeros(M+1, dtype=np.int64)
high_range[1:] = N // A[1:] - np.maximum(M, N // (A[1:] + 1))  # Mはlowerに入れるので0
low = np.zeros(M+1, dtype=np.int64)
high = np.zeros(M+1, dtype=np.int64)
low[1] = 1
for _ in range(K):
    prev_low = low.copy()
    prev_high = high.copy()
    prev_low_cum = prev_low.cumsum() % MOD
    prev_high_cum = prev_high.cumsum() % MOD
    low = np.zeros(M+1, dtype=np.int64)
    low[1:] += (prev_low_cum[-1] + prev_high_cum[-1])
    low[1:] -= prev_high_cum[:-1]
    high = prev_low_cum * high_range
    low %= MOD; high %= MOD

answer = (low[1:].sum() + high[1:].sum()) % MOD
print(answer % MOD)

Submission status: Accepted

Solution code:
from itertools import accumulate

N, K = map(int, input().split())
mod = 10**9 + 7

xs = []
x = 1
while x * x <= N:
    xs.append(N // x)
    x += 1
s = x - 1
y = 1
while y < N // y:
    xs.append(y)
    y += 1
xs = list(set(xs))
xs.sort()
compress = {x : i for i, x in enumerate(xs)}

dp = [[0] * len(compress) for _ in range(K)]
for x, i in compress.items():
    dp[-1][i] = x

for k in range(K-1)[::-1]:
    cum = list(accumulate([0] + dp[k+1]))
    for x, i in compress.items():
        a = max(compress[N // x], compress[N // s])
        dp[k][i] = (cum[-1] - cum[a]) % mod

    b = 1
    cum = [0] * len(compress)
    while b < N // b:
        cnt = N // b - N // (b + 1)
        cum[compress[b]] = (cum[compress[b]] + cnt * dp[k+1][compress[b]]) % mod
        b += 1
    cum = list(accumulate([0] + cum))
    for x, i in compress.items():
        b = N // x
        if x <= b:
            continue
        dp[k][i] += cum[-1] - cum[compress[b]+1]
        dp[k][i] += (x - N // (b + 1)) * dp[k+1][compress[b]]
        dp[k][i] %= mod
print(dp[0][-1])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())

mod=10**9+7

ans=0
L=[[0,0]]
for i in range(1,N+1):
    if i*i==N:
        L.append([i,i])
        break
    elif i*i>N:
        break
    else:
        L.append([N//i,i])
R=[]
for i in range(len(L)):
    if L[-1-i][0]==L[-1-i][1]:
        continue
    else:
        R.append([L[-1-i][1],L[-1-i][0]])
Arr=L+R
#print(Arr)

for i in range(1,len(Arr)):
    ans+=pow(Arr[i][0],K-1,mod)*(Arr[i][1]-Arr[i-1][1])
#print(ans%mod)
DP=[[1 for i in range(len(Arr)-1)]for j in range(K)]
for j in range(len(Arr)-1):
    DP[0][j]=(Arr[j+1][1]-Arr[j][1])
#print(DP)
for i in range(1,K):
    Rui=[DP[i-1][0]]
    for j in range(1,len(Arr)-1):
        Rui.append(Rui[-1]+DP[i-1][j])
    #print(Rui)
    for j in range(len(Rui)):
        DP[i][j]=(Rui[-1-j]*(Arr[j+1][1]-Arr[j][1]))%mod
print(sum(DP[-1])%mod)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	preList = []
	preList2 = []
	for i in range(1, N + 1):
		if i ** 2 == N:
			preList.append(1)
			break
		elif i ** 2 > N:
			break
		else:
			if i == int(N // i):
				preList.append(1)
				break
			else:
				preList.append(int(N // i) - int(N // (i + 1)))
				preList2.append(1)

	start = list(reversed(preList + preList2))
	M = len(start)
	DP = [[0] * M for i in range(K)]
	DP[0] = start


	#DP
	for i in range(1, K):
		Csum = [0] * (M + 1)
		for j in range(M):
			Csum[j + 1] += Csum[j] + DP[i - 1][j]

		for j in range(M):
			DP[i][j] = Csum[M - j] * DP[0][j]
			DP[i][j] %= con
	
	# print(start)
	# print(DP)
	print(sum(DP[K - 1]) % con) 
	




if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
mod = 10**9 + 7

nums = set()
d = {}
for i in range(1,10**6):
    a = n//i
    b = 1 + n//(i+1)
    d[i] = a
    nums.add(i)
    nums.add(a)
    if(i >= b):
        break
    d[b] = i
    nums.add(b)

d = sorted(d.items())

dic_en = {}
dic_de = {}
nums = sorted(list(nums))
cnt = [0] * len(nums)
done = 0
for i,num in enumerate(nums):
    dic_en[num] = i
    dic_de[i] = num
    cnt[i] = num - done
    done = num

d = []
for num in nums:
    d.append((dic_en[num],  dic_en[n//num]))

op = cnt[::]

def update(op):
    n = len(nums)
    res = [0] * (n+1)
    for a,b in d:
        res[0] += op[a]
        res[b+1] -= op[a]
    res[0] %= mod
    for i in range(1,n):
        res[i] += res[i-1]
        res[i] %= mod
    for i in range(n):
        res[i] *= cnt[i]
        res[i] %= mod
    return res[:-1]

for i in range(k-1):
    op = update(op)

ans = sum(op) % mod

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n, k = map(int, input().split())
mod = 10 ** 9 + 7

mx = np.sqrt(n).astype(int)

dp_u = np.ones(mx, np.int64)

N = np.full(mx, n, np.int64)
RNG = np.arange(1, mx + 2)
L = N // RNG[:-1]
R = N // RNG[1:]
R[-1] = np.maximum(R[-1], mx)
coef = L - R
dp_d = coef

for _ in range(2, k + 1):
    acc_u = np.cumsum(dp_u) % mod
    acc_d = np.cumsum(dp_d[::-1])[::-1] % mod
    dp_u = (dp_u.sum() + acc_d) % mod
    dp_d = coef * acc_u % mod

ans = (dp_u.sum() + dp_d.sum()) % mod
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n, k = map(int, input().split())
mod = 10 ** 9 + 7

mx = np.sqrt(n).astype(int)

dp_u = np.ones(mx, np.int64)

N = np.full(mx, n, np.int64)
L = N // np.arange(1, mx + 1)
R = np.maximum(N // np.arange(2, mx + 2), mx)
coef = L - R
dp_d = coef

for _ in range(2, k + 1):
    acc_u = np.cumsum(dp_u) % mod
    acc_d = np.cumsum(dp_d[::-1])[::-1] % mod
    dp_u = (dp_u.sum() + acc_d) % mod
    dp_d = coef * acc_u % mod

ans = (dp_u.sum() + dp_d.sum()) % mod
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n, k = map(int, input().split())
mod = 10 ** 9 + 7

mx = 1
while (mx + 1) ** 2 <= n:
    mx += 1

dp_u = np.ones(mx, np.int64)
N = np.full(mx, n, np.int64)
L = N // np.arange(1, mx + 1)
R = np.maximum(N // np.arange(2, mx + 2), mx)
coef = L - R
dp_d = coef

for _ in range(2, k + 1):
    acc_u = np.cumsum(dp_u) % mod
    acc_d = np.cumsum(dp_d[::-1]) % mod
    dp_u = (dp_u.sum() + acc_d[::-1]) % mod
    dp_d = coef * acc_u % mod

ans = (dp_u.sum() + dp_d.sum()) % mod
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

N,K=map(int,input().split())
mod=10**9+7

m=int(sqrt(N))
if N//(m+1)==m:
    dp=[[[0  for i in range(0,2)] for j in range(0,int(sqrt(N)))] for k in range(0,K+1)]

    for i in range(0,int(sqrt(N))):
        dp[1][i][1]=1
        dp[1][i][0]=(N//(i+1)-N//(i+2))

    for k in range(2,K+1):
        s=0
        for i in range(0,int(sqrt(N))):
            s=(s+dp[k-1][i][1])%mod
            dp[k][i][0]=(s*(N//(i+1)-N//(i+2)))%mod

        for j in range(0,int(sqrt(N))):
            i=int(sqrt(N))-j-1
            s=(s+dp[k-1][i][0])%mod
            dp[k][i][1]=s

    ans=sum(dp[K][i][0]+dp[k][i][1] for i in range(0,int(sqrt(N))))%mod
    print(ans)

else:
    dp0=[[0 for i in range(0,int(sqrt(N))-1)] for k in range(0,K+1)]
    dp1=[[0 for i in range(0,int(sqrt(N)))] for k in range(0,K+1)]

    for i in range(0,int(sqrt(N))-1):
        dp0[1][i]=(N//(i+1)-N//(i+2))
        dp1[1][i]=1

    dp1[1][-1]=1

    for k in range(2,K+1):
        s=0
        for i in range(0,int(sqrt(N))-1):
            s=(s+dp1[k-1][i])%mod
            dp0[k][i]=(s*(N//(i+1)-N//(i+2)))%mod

        s=(s+dp1[k-1][int(sqrt(N))-1])%mod
        dp1[k][int(sqrt(N))-1]=s%mod
        for j in range(1,int(sqrt(N))):
            i=int(sqrt(N))-j-1
            s=(s+dp0[k-1][i])%mod
            dp1[k][i]=s

    ans=sum(dp0[K][i]+dp1[K][i] for i in range(0,int(sqrt(N))-1))%mod
    ans=(ans+dp1[K][-1])%mod

    print(ans)