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: Accepted

Solution code:
from math import sqrt, floor
N, K = map(int, input().split())
mod = 10**9+7

sn = floor(sqrt(N))
t = N//(sn + 1)

dp1 = [0] + [1]*sn + [0]
dp2 = [0] + [N//j - N//(j+1) for j in range(1, t+1)]
dp2 += [0]*(len(dp1) - len(dp2))
C = dp2[:]
for _ in range(K-1):
    d1 = [0]*(sn + 2)
    d2 = [0]*(sn + 2)
    
    sumd1 = 0
    for d in dp1[1:]:
        sumd1 = (sumd1 + d) % mod
    
    d1[1] = sumd1
    
    for i in range(1, sn+1):
        d2[i] = (d2[i] + dp1[i]) % mod
        d1[1] = (d1[1] + dp2[i]) % mod
        d1[i+1] = (d1[i+1] - dp2[i]) % mod
    
    for i in range(1, sn+2):
        dp1[i] = (d1[i] + dp1[i-1])%mod
        dp2[i] = (d2[i] + dp2[i-1])%mod
    dp1[-1] = 0
    
    dp2 = [d*c%mod for d, c in zip(dp2, C)]
ans = 0
for d in dp1:
   ans = (ans + d)%mod
for d in dp2:
    ans = (ans + d)%mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(N: int, K: int):
    ns = []
    for i in range(1, N + 1):
        if N < i * i:
            break
        ns.append(i)
        ns.append(N // i)
    ns = sorted(list(set(ns)))

    m = {n: i for i, n in enumerate(ns)}
    l = [1] * len(ns)
    for i, (s, b) in enumerate(zip(ns, ns[1:])):
        l[i] = (N // s) - (N // b)

    dp = [[0] * len(ns) for _ in range(K+1)]
    dp[0][m[N]] = 1

    for i in range(K):
        for j in range(len(ns) - 2, -1, -1):
            dp[i][j] += dp[i][j + 1]
        for j, nn in enumerate(ns):
            nj = m[N // nn]
            dp[i+1][j] = (dp[i+1][j] + dp[i][nj] * l[j]) % MOD

    return sum(dp[-1]) % MOD


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    result = solve(N, K)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def hersCode(l, r, n, N):
  ok = l
  ng = r + 1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if mid * n <= N:
      ok = mid
    else:
      ng = mid
  return ng


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

if N == 1:
  print(1)
  exit()

L = []
t = 1
n = N
while t <= N:
  L.append(t)
  t = hersCode(t, N, N // t ,N)

D = [0] * len(L)
L.append(N + 1)
for i in range(len(L) - 1):
  D[i] = (L[i + 1] - L[i]) % MOD
DP = [[0] * (len(D)) for _ in range(K)]
for i in range(len(D)):
  DP[0][i] = D[i]

for i in range(1, K):
  S = [0] * len(D)
  S[0] = DP[i - 1][0]
  for j in range(1, len(D)):
    S[j] = S[j - 1] + DP[i - 1][j]
  for j in range(len(D)):
    DP[i][j] = S[-1 -j] * D[j] % MOD

print(sum(DP[K - 1]) % MOD)

Submission status: Accepted

Solution code:
# from https://atcoder.jp/contests/abc132/submissions/6187293

def main():
    N, K = map(int, input().split())

    MOD = 10 ** 9 + 7
    r = int(N ** 0.5 + 1)
    z = [i for i in range(r)] + [N // i for i in range(1, r)][::-1]
    m = len(z)
    pre = [0] + [1] * (m - 1)
    for _ in range(1, K+1):
        dp = [0] * m
        for i in range(1, m):
            dp[i] = (dp[i-1] + pre[m-i] * (z[i] - z[i-1])) % MOD
        pre = dp
    print(dp[-1])


main()

Submission status: Accepted

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

m = n ** 0.5
cnt = [n // i - n // (i + 1) for i in range(1, int(m) + 1)] 
cnt = np.array((cnt + [1 for _ in range(n - sum(cnt))])[::-1])
nxt = cnt[:]
for _ in range(k - 1):
	cnt = nxt * np.cumsum(cnt)[::-1] % mod

print(sum(cnt) % mod)

Submission status: Accepted

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

import math
SQ=int(math.sqrt(N))

DP1=[1]*(SQ+1)
DP1[0]=0


DP2=[]

k=SQ

for i in range(SQ,0,-1):
    DP2.append(N//i-k)
    k=N//i


KOSUU2=[v for v in DP2]

#print(DP1)
#print(DP2)
#print()

for j in range(K-1):
    NDP1=[0]*(SQ+2)
    NDP2=[0]*(SQ+1)

    for j in range(1,SQ+1):
        NDP2[-j]-=DP1[j]
        NDP1[1]+=DP1[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(-1,-SQ-1,-1):
        NDP1[-j+1]-=DP2[j]
        NDP1[1]+=DP2[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(1,SQ+2):
        NDP1[j]+=NDP1[j-1]

    NDP2[0]+=NDP1[-1]

    for j in range(1,SQ+1):
        NDP2[j]+=NDP2[j-1]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(SQ):
        NDP2[j]=NDP2[j]*KOSUU2[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    DP1=[n%mod for n in NDP1[:SQ+1]]
    DP2=[n%mod for n in NDP2[:SQ]]

    
print((sum(DP1)+sum(DP2))%mod)

Submission status: Accepted

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

i = 1
n = []
while i <= N :
    j = N // i
    if i <= j :
        n.append(1)
        i += 1
    else :
        n.append(N//j-i+1)
        i = N // j + 1

M = len(n)

dp = [[0] * M for _ in range(K)]
dp[0] = n

for k in range(1, K) :
    sdp = [0] * M
    sdp[0] = dp[k-1][0]
    for i in range(1, M) :
        sdp[i] = (sdp[i-1] + dp[k-1][i]) % MOD
    for i in range(M) :
        dp[k][i] = sdp[M-i-1] * n[i] % MOD

ret = 0

for j in range(M) :
    ret += dp[K-1][j]
    ret %= MOD
    
print(ret)

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

MOD = 10 ** 9 + 7
N, K = list(map(int, sys.stdin.readline().split()))

# ある程度数をまとめられるのでまとめておく
nexts = []
n = N
while True:
    p = int(N // (int(N // n) + 1))
    nexts.append(n)
    if p <= 0:
        break
    n = p

# dp[k][i]: i に続く k 文字のパターン数
dp = defaultdict(lambda: defaultdict(int))
prev = 0
for n, m in zip(nexts, reversed(nexts)):
    dp[0][m] = m
for k in range(1, K):
    dp[k][0] = 0
    prev = 0
    for n, m in zip(nexts, reversed(nexts)):
        dp[k][m] = (dp[k][prev] + dp[k-1][n] * (m-prev)) % MOD
        prev = m
print(dp[K - 1][N])

Submission status: Accepted

Solution code:
import math
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

MOD = 10 ** 9 + 7
N, K = list(map(int, sys.stdin.readline().split()))

NM = []
prev = 0
for i in range(1, int(math.sqrt(N)) + 2):
    m = int(N // i)
    NM.append(N - m - prev)
    prev = N - m

cnt = N
nums = []
while cnt >= 1:
    nums.append(cnt)
    i = int(N // cnt)
    p = NM[i] if i < len(NM) else 1
    cnt -= p
nums.reverse()

# dp[k][n]: rec(n, k)
dp = defaultdict(lambda: defaultdict(int))
for n in nums:
    dp[1][n] = n
for k in range(2, K + 1):
    for n in nums:
        i = int(N // n)
        p = NM[i] if i < len(NM) else 1
        ret = dp[k - 1][i] * p % MOD
        cum = dp[k][n - p]
        dp[k][n] = (cum + ret) % MOD

ans = dp[K][N]
print(ans % MOD)

# ans = rec(N, K)
# print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import deque
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

# guchoku case

# dp = [[0 for _ in range(N+1)] for _ in range(K+1)]

# for i in range(N+1):
#     dp[1][i] = 1
# for i in range(K):
#     for j in range(1,N+1):
#         for k in range(1, N // j + 1):
#             dp[i+1][j] += dp[i][k]
#             dp[i+1][j] %= MOD

JN = deque()  # N//j table
SQN = int(N**0.5)
JN.append(SQN)

if SQN**2 != N:
    JN.append(N//SQN)
for j in range(SQN-1, 0, -1):
    JN.appendleft(j)
    JN.append(N//j)
JN.appendleft(0)

# JN.sort()
# PJN = {JN[i]: JN[i-1] for i in range(1, len(JN))}  # prev jn
LJN = len(JN)

dp = [[0 for _ in range(LJN)] for _ in range(K)]
cdp = [[0 for _ in range(LJN)] for _ in range(K)]
w = [0 for _ in range(LJN)]

# init dp
prv = 0
for i in range(1,LJN):
    jn = JN[i]
    dp[0][i] = 1
    w[i] = jn - prv
    cdp[0][i] = jn
    prv = JN[i]

for i in range(K-1):
    for j in range(1,LJN):
        dp[i+1][j] = cdp[i][LJN-j]
        dp[i+1][j] %= MOD
        cdp[i+1][j] = cdp[i+1][j-1] + dp[i+1][j] * w[j]
        cdp[i+1][j] %= MOD

print(cdp[-1][-1])

Submission status: Accepted

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

MOD = 10 ** 9 + 7

spl = int(N ** 0.5) + 1
l = list(range(spl)) + [N // i for i in reversed(range(1, spl))]
m = 2 * spl - 1

for i in reversed(range(m - 1)):
    l[i + 1] -= l[i]

dp = [l[:]] + [[0] * m for _ in range(K - 1)]
for i in range(K - 1):
    for j in range(m - 1):
        dp[i][j + 1] += dp[i][j]
        dp[i][j + 1] %= MOD

    for j in range(1, m):
        dp[i + 1][-j] = dp[i][j] * l[-j] % MOD

ans = 0
for v in dp[-1][1:]:
    ans += v
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate as ac
N,K=map(int,input().split())
n=int(N**0.5)
mod=10**9+7
list_a=[1]*n
list_b=[N//j-N//(j+1) for j in range(1,n)]+[(N//n-n)]
list_p=[p for p in list_b]
list_aa=list(ac(list_a))
list_bb=list(reversed(list(ac(reversed(list_b)))))

for i in range(K-1):
    temp=sum(list_a)
    list_a=[(temp+list_bb[j])%mod for j in range(n)]
    list_b=[(list_p[j]*list_aa[j])%mod for j in range(n)]
    list_aa=list(ac(list_a))
    list_bb=list(reversed(list(ac(reversed(list_b)))))
    
print((sum(list_a+list_b))%mod)

Submission status: Accepted

Solution code:
from itertools import accumulate
def BC132_F():
    n, k = list(map(int, input().split(' ')))
    mod = 10**9 + 7
    sqt = int(n**0.5)
    cnt = [n // i - n // (i + 1) for i in range(1, n // sqt)] + [1] * sqt
    x = cnt
    for _ in range(k):
        x = [(i * j) % mod for i, j in zip(accumulate(reversed(x)), cnt)]
    return x[-1]


print(BC132_F())

Submission status: Accepted

Solution code:
from itertools import accumulate as r;n,k=map(int,input().split());m=10**9+7;j=int(n**0.5);c=[n//(i+1)-n//(i+2) for i in range(n//(j+1))]+[1]*j;x=c;exec("x=[(y*d)%m for y,d in zip(r(x[::-1]),c)];"*k);print(x[-1])

Submission status: Accepted

Solution code:
from itertools import accumulate

N,K = map(int, input().split())
As = [] 
for i in range(1,int(N**0.5)+1):
    As.append(i)
    if N//i != i:
        As.append(N//i)
As = sorted(As,reverse=False)
nums = []
for i in range(len(As)-1):
    nums.append(As[i+1]-As[i])
nums = [1] + nums
nums.reverse()
mod = 10**9 + 7
ans = 0
dp = [[0] * len(As) for i in range(K+1)]


dp[0][0] = 1
for i in range(K):
    # 1だと全通り分が成り立つし、Nだと1通り。
    # それぞれ種別にまとまっているので、それらをかける
    acc = list(accumulate(dp[i]))
    for j in range(len(As)):
        dp[i+1][len(As)-j-1] = acc[j]*nums[j]%mod
print(sum(dp[K])%mod)

Submission status: Accepted

Solution code:
def main():
     MOD=10**9+7
     n,k=map(int,input().split())
     t=[]#ｔ＝n//jの種類を数えるのに使う
     t_cnt=[]#tとなるjの個数
     cnt=[0]
     for i in range(1,int(n**0.5)+1):
          tmp=n//i
          if tmp not in t:
               t.append(tmp)
               t_cnt.append(1)
          else:
               cnt[-1]+=tmp
               t_cnt[-1]+=1
     for tmp in range(t[-1]-1,0,-1):
          tmp_j=n//(tmp)-n//(tmp+1)
          if tmp_j!=0:
               t.append(tmp)
               t_cnt.append(tmp_j)
     
     cnt=[]
     now=0
     for i in range(len(t)):
          now+=t[i]*t_cnt[i]
          cnt.append(now)
     kind=len(cnt)
     dp=[cnt]+[[0]*kind for i in range(k-2)]
     
     for i in range(1,k-1):
          for j in range(kind):
               dp[i][j]=(dp[i-1][kind-j-1]*t_cnt[j]+dp[i][j-1])%MOD
     print(dp[-1][-1])
     return
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

MOD = 10**9 + 7


def main():
    N, K = map(int, input().split())
    R = int(math.sqrt(N))
    if N // R == R:
        M = R * 2 - 1
    else:
        M = R * 2
    mapping = [0] * (M+1)
    for i in range(1, R+1):
        mapping[i] = i
        mapping[-i] = N//i
    cnt = [0] * (M+1)
    for i in range(1, M+1):
        cnt[i] = mapping[i] - mapping[i-1]
    dp = [[0] * (M+1) for _ in range(K+1)]
    dp[0] = list(cnt)
    for i in range(M):
        dp[0][i+1] += dp[0][i]

    for i in range(K-1):
        for j in range(1, M+1):
            if j <= R:
                idx = -j
            else:
                idx = M - j + 1
            dp[i+1][j] = dp[i][idx]
        for j in range(M):
            dp[i+1][j+1] = (dp[i+1][j] + dp[i+1][j+1] * cnt[j+1]) % MOD
    print(dp[K-1][M])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
N,K=map(int,input().split())
N_s=int(N**0.5)
list_a=[1]*N_s
list_b=[N//j-N_s for j in range(1,N_s+1)]
list_p=[N//j-N_s for j in range(1,N_s+1)]
for p in range(1,len(list_p)):
        list_p[p-1]=list_p[p-1]-list_p[p]
        
for p in range(1,len(list_b)):
    list_b[p-1]=list_b[p-1]-list_b[p]

list_bb=list(reversed(list(accumulate(reversed(list_b)))))
list_aa=list(accumulate(list_a))

mod=10**9+7

for i in range(K-1):
    temp=sum(list_a)
    list_an=[(temp+list_bb[j])%mod for j in range(N_s)]
    list_bn=[(list_p[j-1]*list_aa[j-1])%mod for j in range(1,N_s+1)]

    list_bbn=list(reversed(list(accumulate(reversed(list_bn)))))
    list_aa=list(accumulate(list_an))
    list_a=list_an
    list_b=list_bn
    list_bb=list_bbn
    
print((sum(list_a)+sum(list_b))%mod)

Submission status: Accepted

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

    U = []; V = []
    for x in range(1, int(N**.5)+1):
        U.append(x)
        if x < N//x:
            V.append(N//x)
    V.reverse(); U.extend(V)

    L = len(U)
    prv = 0
    R = []
    for x in U:
        R.append(x-prv)
        prv = x
    def gen(it):
        MOD = 10**9 + 7
        r = 0
        for p, s in it:
            r = (p * s + r) % MOD
            yield r

    S = [1]*(L+1)
    S[-1] = 0
    for k in range(K):
        S[L-1::-1] = gen(zip(R, S))
    print(S[0])
solve()

Submission status: Accepted

Solution code:
import sys
def solve():
    N, K = map(int, input().split())
    MOD = 10**9 + 7

    U = []; V = []
    for x in range(1, int(N**.5)+1):
        U.append(x)
        if x < N//x:
            V.append(N//x)
    V.reverse(); U.extend(V)

    L = len(U)
    prv = 0
    R = []
    for x in U:
        R.append(x-prv)
        prv = x
    def gen(R, S):
        r = 0
        for p, s in zip(R, S):
            r = (p * s + r) % MOD
            yield r

    S = [1]*(L+1)
    S[-1] = 0
    for k in range(K):
        S[L-1::-1] = gen(R, S)
    print(S[0])
solve()

Submission status: Accepted

Solution code:
mod=1000000007
n,k=map(int,input().split())
s=int(n**0.5)
Num=[0]*(s+1)
for i in range(s,0,-1):
    Num[i]=i
    Num.append(n//i)
l=len(Num)
for i in range(1,l):
    Num[-i]=Num[-i]-Num[-i-1]
DP=[[0]*l for _ in range(k)]
DP[0]=Num[:]
for i in range(1,k):
    tmp=0
    for j in range(1,l):
        tmp+=DP[i-1][j]
        tmp%=mod
        DP[i][-j]=(tmp*Num[-j])%mod
ans=0
for i in DP[-1][1:]:
    ans+=i
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import math
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

R = 10**9+7
n,k = inm()
q = int(math.sqrt(n))
a = [ [0]*(q+1) for j in range(k) ]
b = [ [0]*(q+1) for j in range(k) ]
c = [0]*(q+1)
c[1] = n - n//2
for i in range(2,q):
    c[i] = n//i - n//(i+1)
c[q] = n//q - q
for i in range(1,q+1):
    a[0][i] = 1
    b[0][i] = c[i]


for j in range(1,k):
    aacc = [0]*(q+2)
    bacc = [0]*(q+2)
    for i in range(1,q+1):
        aacc[i] = (aacc[i-1] + a[j-1][i])%R
    for i in range(q,0,-1):
        bacc[i] = (bacc[i+1] + b[j-1][i])%R
    for i in range(1,q+1):
        a[j][i] = (aacc[q]+bacc[i])%R
        b[j][i] = (aacc[i]*c[i])%R

print( (sum(a[k-1]) + sum(b[k-1])) % R )

Submission status: Accepted

Solution code:
import numpy as np

n, k = list(map(int, input().split()))
MOD = 10 ** 9 + 7
l = int(n ** 0.5)
coe = [n // i - l for i in range(l, 0, -1)]
coe.append(0)
coe.reverse()
coe = np.array(coe, dtype=np.int64)

dp1 = np.ones(l + 1, dtype=np.int64)
dp2 = coe.copy()
dp1[0] = 0
for i in range(k - 1):
    dp1acc_f = np.add.accumulate(dp1) % MOD
    dp1acc_b = np.add.accumulate((dp1 * coe % MOD)[::-1])[::-1] % MOD
    s = dp1acc_f[-1]
    dp1acc_f = np.roll(dp1acc_f, 1)
    dp1[1:] = (s + dp2[1:]) % MOD
    dp2[1:] = (dp1acc_b + dp1acc_f * coe)[1:] % MOD
ans = (dp1.sum() + dp2[1]) % MOD
print(ans)

Submission status: Accepted

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

sq = 0
while (sq + 1) * (sq + 1) <= N:
    sq += 1

num = [0 for i in range(2 * sq + 1)]
for i in range(1, sq + 1):
    num[i] = 1
for i in range(1, sq + 1):
    lo = max(sq + 1, (N + i + 1) // (i + 1))
    hi = N // i
    num[2 * sq + 1 - i] = hi - lo + 1

dp = [[0 for j in range(2 * sq + 2)] for i in range(K + 1)]
dp[0][1] = 1
for i in range(K):
    for j in range(1, 2 * sq + 1):
        ways = dp[i][j] * num[j] % MOD
        dp[i + 1][1] += ways
        dp[i + 1][2 * sq + 2 - j] -= ways
    for j in range(1, 2 * sq + 1):
        dp[i + 1][j] += dp[i + 1][j - 1]

ans = 0
for j in range(1, 2 * sq + 1):
    ans += dp[K][j] * num[j]
print(ans % MOD)

Submission status: Accepted

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については、個数にわたって合計をとる
lower = np.zeros(M+1, dtype=np.int64)
upper = np.zeros(M+1, dtype=np.int64)
# 0項目に1を置いておくとする
lower[1] = 1
for k in range(1,K+1):
    prev_lower = lower
    prev_upper = upper
    np.cumsum(prev_lower, out = prev_lower)
    np.cumsum(prev_upper, out = prev_upper)
    prev_lower %= MOD
    prev_upper %= MOD
    # 下側 to 下側
    lower = np.zeros(M+1, dtype=np.int64)
    lower += (prev_lower[-1] + prev_upper[-1])
    lower[1:] -= prev_upper[:-1] # 商がn-1以下だと受け付けない
    lower[0] = 0
    # 上側 to 上側：ないはず
    # 下側 to 上側：
    upper = prev_lower * upper_cnt
    lower %= MOD
    upper %= MOD
    
answer = (lower.sum() + upper.sum()) % MOD
print(answer)

Submission status: Accepted

Solution code:
n, k = [int(x) for x in input().strip().split(" ")]
mod = pow(10, 9) + 7

ll = []
ks = []
cc = 0
last = 0
for i in range(n):
    i += 1
    if n//i < i:
        last = n//i
        break
    ll.append(n//i)
    ks.append(1)
    last = n//i
    cc += 1

while True:
    if last == 0:
        break
    if last >= len(ll):
        mm = last
    else:
        mm = ll[last]
    ll.append(last * (ll[last-1] - mm))
    ks.append((ll[last-1] - mm))
    last -= 1
n_l = len(ll)

for _ in range(k-2):
    nll = []
    m = sum(ll) % mod
    for i in range(n_l):
        x = n_l - i - 1
        nll.append((m * ks[i]) % mod)
        m -= (mod + ll[x]) % mod
    ll = nll[:]
print(sum(ll) % mod)

Submission status: Accepted

Solution code:
import numpy as np

n, k = list(map(int, input().split()))
MOD = 10 ** 9 + 7
l = int(n ** 0.5)
coe = []
for i in range(l, 0, -1):
    coe.append(n // i - l)
coe.append(0)
coe.reverse()
coe = np.array(coe, dtype=np.int64)

dp1 = np.ones(l + 1, dtype=np.int64)
dp2 = coe.copy()
dp1[0] = 0
for i in range(k - 1):
    dp1acc = np.add.accumulate(dp1) % MOD
    dp12acc = np.add.accumulate((dp1 * coe % MOD)[::-1])[::-1]
    s = dp1acc[-1]
    dp1acc = np.roll(dp1acc, 1)
    dp1acc[0] = 0
    dp12acc[0] = 0
    dp1[1:] = (s + dp2[1:]) % MOD
    dp2 = dp12acc + dp1acc * coe % MOD
ans = (dp1.sum() + dp2[1]) % MOD
print(ans)

Submission status: Accepted

Solution code:
n,k = [int(x) for x in input().split()]
mod = 1000000007
if n == 1:
    print(1)
    quit()
f = [0,n]
i = 1
while f[i] >= i:
    i += 1
    f.append(n//i)
s = [0]*len(f)
for i in range(1,len(f)):
    s[i] = 1
for i in range(2,len(f))[::-1]:
    if f[i] <= i:
        s[-1] = f[i-1]-f[i]
    else:
        s.append(f[i-1]-f[i])
MA = len(s)
dp = [[0]*MA for i in range(k)]
dp[0] = [s[i] for i in range(MA)]
for i in range(MA-1):
    dp[0][i+1] += dp[0][i]
    dp[0][i+1] %= mod
for l in range(k-1):
    for i in range(1,MA):
        j = MA-i
        dp[l+1][i] += dp[l][j]*s[i]
        dp[l+1][i] %= mod
        dp[l+1][i] += dp[l+1][i-1]
        dp[l+1][i] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
MOD = 10**9 + 7

U = [0]; V = []
for x in range(1, int(N**.5)+1):
    U.append(x)
    if x < N//x:
        V.append(N//x)
V.reverse(); U.extend(V)

L = len(U)
S = [1]*L
S[0] = 0
for k in range(K-1, -1, -1):
    T = [0]*L
    r = 0
    for i in range(1, L):
        x = U[i-1]; y = U[i]
        T[i] = r = ((y - x) * S[L-i] + r) % MOD
    S = T
print(S[-1])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    d = defaultdict(int)
    for i in s:
        d[i] += 1
    for i in d.keys():
        if d[i] != 2:
            print("No")
            quit()
    print("Yes")
    return

#B
def B():
    n = I()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        k = p[i-1:i+2]
        k.sort()
        if k[1] == p[i]:
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    d = LI()
    d.sort()
    print(d[n//2]-d[n//2-1])
    return

#D
def D():
    n,k = LI()
    fact = [1]*100001
    for i in range(1,100001):
        fact[i] = fact[i-1]*i%mod
    inv = [1]*100001
    inv[-1] = pow(fact[-1],mod-2,mod)
    for i in range(1,100001)[::-1]:
        inv[i-1] = inv[i]*i%mod

    for i in range(1,k+1):
        if n-k+1 < i:
            print(0)
        else:
            ans = fact[n-k+1]*inv[i]*inv[n-k+1-i]%mod
            ans *= fact[k-1]*inv[k-i]*inv[i-1]%mod
            ans %= mod
            print(ans)
    return

#E
def E():
    ma = 100000000
    def dijkstra(s):
        d = defaultdict(lambda : ma)
        q = [(0,s,0)]
        d[(s,0)] = 0
        while q:
            dx,x,t = heappop(q)
            t = (t+1)%3
            k = t == 1
            for y in v[x]:
                if dx+k < d[(y,t)]:
                    d[(y,t)] = dx+k
                    heappush(q,(d[(y,t)],y,t))
        res = d[(g,0)]
        if res == ma:
            res = -1
        return res

    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
    s,g = LI()
    s -= 1
    g -= 1
    print(dijkstra(s))
    return

#F
def F():
    n,k = LI()
    if n == 1:
        print(1)
        quit()
    f = [0,n]
    i = 1
    while f[i] >= i:
        i += 1
        f.append(n//i)
    s = [0]*len(f)
    for i in range(1,len(f)):
        s[i] = 1
    for i in range(2,len(f))[::-1]:
        if f[i] <= i:
            s[-1] = f[i-1]-f[i]
        else:
            s.append(f[i-1]-f[i])
    MA = len(s)
    dp = [[0]*MA for i in range(k)]
    dp[0] = [s[i] for i in range(MA)]
    for i in range(MA-1):
        dp[0][i+1] += dp[0][i]
        dp[0][i+1] %= mod
    for l in range(k-1):
        for i in range(1,MA):
            j = MA-i
            dp[l+1][i] += dp[l][j]*s[i]
            dp[l+1][i] %= mod
            dp[l+1][i] += dp[l+1][i-1]
            dp[l+1][i] %= mod
    print(dp[-1][-1])
    return


#Solve
if __name__ == "__main__":
    F()

Submission status: Accepted

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

# SQRT
R = 1
while (R + 1) ** 2 < N:
    R += 1

square = False
if (R + 1) ** 2 == N:
    square = True


DP_S = [1] * R
DP_L = [1] * R
N_L = [1] * R
DP_M = 0
L = R
if square:
    DP_M = 1
    L += 1


for i in range(R, 0, -1):
    Q = N // i
    DP_L[i - 1] = Q - L
    N_L[i - 1] = Q - L
    L = Q

for _ in range(K - 1):
    S = 0
    L = sum(DP_L) + DP_M
    SS = sum(DP_S)
    for i in range(R):
        S = (S + DP_S[i]) % LARGE
        DP_S[i] = (L + SS) % LARGE
        L = (L - DP_L[i]) % LARGE
        DP_L[i] = (S * N_L[i]) % LARGE

    if square:
        DP_M = (DP_M + SS) % LARGE

print((sum(DP_L) + sum(DP_S) + DP_M) % LARGE)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
MOD = 10**9+7

from math import sqrt, floor

n,k = [int(i) for i in input().split()]
sn = floor(sqrt(n))+1

pre = [0]*sn
pre[1] = 1

cur = [1]*(sn)
cur[0] = 0

#big = n-sn+1

for _ in range(k-1):
#    print(cur)
    new = [sum(cur)%MOD]*(sn); new[0] = 0
    s = sum(pre)%MOD
    b=0
    res=0
    for j in range(sn-1,0,-1):
        a = n//j - (sn-1) #okな個数
        res += (a-b)*s
        res %=MOD
        new[j] += res
        if new[j] > MOD: new[j] -= MOD
        s -= pre[j]
        b=a
        
    pre,cur = cur,new


#print(pre,cur)
ans =0
for j in range(sn-1,0,-1):
    ans += pre[j]*(n//j - (sn-1))
    ans %=MOD


print((sum(cur)+ans)%MOD)

Submission status: Accepted

Solution code:
from math import sqrt
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, K = inpl()
sqN = int(sqrt(N))
bound = [0]*(sqN+2)
for i in range(1,sqN+2):
    bound[i] = N//i
bound[sqN+1] = sqN
group_size = [0]*(sqN+1)
for i in range(1,sqN+1):
    group_size[i] = bound[i]-bound[i+1]

cur_small = [1] * (sqN+1)
cur_small[0] = 0
cur_large = [ s for s in group_size ]
for k in range(K-1):
    prev_small = cur_small
    cur_small = [0] * (sqN+2)
    prev_large = cur_large
    cur_small = [0] * (sqN+2)
    cur_small[sqN+1] = sum(prev_small[:sqN+1])
    for n in range(sqN,0,-1):
        cur_small[n] = (prev_large[n] + cur_small[n+1]) % MOD
    acc_prev_small = 0
    for n in range(1,sqN+1):
        acc_prev_small += prev_small[n]
        cur_large[n] = acc_prev_small*group_size[n] % MOD

print((sum(cur_small[:sqN+1])+sum(cur_large[:sqN+1]))%MOD)

Submission status: Accepted

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

mod = 10**9 + 7

ans_array = []
divide_max = N
divide_count = []

for i in range(2, math.floor(math.sqrt(N)) + 2):
    divide = math.floor(N / i)
    ans_array.append(divide_max - divide)
    divide_count.append(divide_max - divide)
    divide_max = divide

for i in range(divide):
    ans_array.append(1)
ans_array = ans_array[::-1]
# print(ans_count)
ans_length = len(ans_array)
ans_acc = [0] * ans_length

for k in range(2, K + 1):
    ans_acc[0] = ans_array[0]
    for i in range(1, ans_length):
        ans_acc[i] = (ans_acc[i - 1] + ans_array[i]) % mod
    # print(ans_array)
    # print(ans_acc)
    for i in range(divide):
        ans_array[i] = ans_acc[ans_length - i - 1]
    for i in range(divide, ans_length):
        ans_array[i] = ans_acc[ans_length - i - 1] * divide_count[
            ans_length - 1 - i] % mod

ans_acc[0] = ans_array[0]
for i in range(1, ans_length):
    ans_acc[i] = (ans_acc[i - 1] + ans_array[i]) % mod

print(ans_acc[-1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=int(n**0.5)
mod=10**9+7
l=[0]*(a+1)
for i in range(a,0,-1):
    l[i]=i
    l.append(n//i)
for i in range(1,2*a+1):
    l[-i]=l[-i]-l[-i-1]
dp=[l]+[[0]*(2*a+1) for i in range(k-1)]
for i in range(1,k):
    t=0
    for j in range(1,2*a+1):
        t+=dp[i-1][j]
        t%=mod
        dp[i][-j]=t*l[-j]%mod
ans=0
for i in dp[-1][1:]:
    ans+=i
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
mod = 1000000007

s = int(math.sqrt(n))
dp = [1] * (n//s+1)
ep = [0] * s
dp[0] = 0

for i in range(1,s):
    ep[i] = 1 # n//i-n//(i+1)

for z in range(k-1):
    ndp = [0] * (n//s+1)
    nep = [0] * s

    for i in range(1,n//s+1):
        if i < s:
            nep[i] += dp[i]
        else:
            ndp[n//i] += dp[i]
    for i in range(1,s):
        ndp[i] += ep[i] * (n//i-n//(i+1))
        ndp[i] %= mod
    for i in range(2, s):
        nep[i] += nep[i-1]
        if nep[i] >= mod:
            nep[i] -= mod
    ndp[n//s] += nep[-1]
    ndp[n//s] %= mod
    for i in range(n//s-1, 0, -1):
        ndp[i] += ndp[i+1]
        if ndp[i] >= mod:
            ndp[i] -= mod
    dp, ep = ndp, nep

ans = sum(dp)
for i in range(1, s):
    ans += ep[i] * (n//i-n//(i+1))
print(ans%mod)

Submission status: Accepted

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

Submission status: Runtime Error

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

mod = 10**9+7

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: Runtime Error

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

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

for i in range(K):
    for j in range(1, N+1):
        for k in range(1, (N//j)+1):
            dp[i+1][k] += dp[i][j]

print(sum(dp[-1]))