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: Wrong Answer

Solution code:
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())
parts = [[n + 1, n + 1]]
i = 1
s = 0
l = n + 1
for i in range(1, n + 1):
    r = n // i - n // (i + 1)
    parts.append([l - 1, l - r])
    l -= r
    if r == 1:
        for i in range(l - 1, 0, -1): parts.append([i, i])
        break
parts = [j for j, i in parts]
nparts = [n // parts[i] - n // parts[i - 1] for i in range(1, len(parts))]

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: Wrong Answer

Solution code:
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())
parts = [[n + 1, n + 1]]
i = 1
s = 0
l = n + 1
for i in range(1, n + 1):
	r = n // i - n // (i + 1)
	parts.append([l - 1, l - r])
	l -= r
	if r == 1:
		for i in range(l - 1, 0, -1): parts.append([i, i])
		break
parts = [j for j, i in parts]
nparts = [n // parts[i] - n // parts[i - 1] for i in range(1, len(parts))]

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))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
sqt = int(n ** 0.5)
dp_mul_num = [1] * sqt + [n // i - n // (i + 1) for i in range(1, sqt + 1)][::-1]
group_num = len(dp_mul_num)
dp = [[0] * group_num for _ in range(k)]
dp[0] = dp_mul_num





for i in range(k - 1):
    ret = 0
    for j in range(group_num):
        ret = (ret + dp[i][j]) % mod
        dp[i + 1][group_num - j - 1] = ret * dp_mul_num[group_num - j - 1] % mod




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

Submission status: Wrong Answer

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 + 10):
    # [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: Wrong Answer

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]
        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: Wrong Answer

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]
        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: Wrong Answer

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)):
    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: Wrong Answer

Solution code:
from bisect import bisect_left
n,k=map(int,input().split())
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: Wrong Answer

Solution code:
from bisect import bisect_left
n,k=map(int,input().split())
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]
print(sum(dp[-1])%mod)

Submission status: Wrong Answer

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 = math.floor(math.sqrt(N))
    B = math.floor(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])%mod
        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%mod)
    exit()

Submission status: Wrong Answer

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 = math.floor(math.sqrt(N))
    B = math.floor(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: Wrong Answer

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

N, K = map(int, input().split())
import math
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)
    exit()


else:
    # N>100
    ans = 0
    L = math.floor(math.sqrt(N))
    B = math.floor(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: Wrong Answer

Solution code:
n,k = map(int,input().split())
mod = 10**+7
sub = int(n**0.5)
p = [1]*(sub)
ps = [i for i in range(1,sub+1)]
l = [i for i in range(1,sub+1)]
sub = n//l[-1]
while sub > 1:
    sub -= 1
    nex = n//sub
    if nex <= l[-1]:
        sub -=1
        nex = n//sub
    dis = nex-l[-1]
    l.append(nex)
    p.append(dis)
    ps.append(ps[-1]+dis)
x = len(p)
dp = [[0]*x for i in range(k)]
dps = [[0]*x for i in range(k)]
dp[0] = p
dps[0] = ps
for i in range(1,k):
    for j in range(x):
        dp[i][j] += dps[i-1][-1-j]*dp[0][j]
        dp[i][j] %= mod
        dps[i][j] = dps[i][j-1]+dp[i][j]
        dps[i][j] %= mod

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

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

@lru_cache
def dfs(i, ub):
    if i == K:
        return 1
    ret = 0
    x = 1
    while x <= ub and x * x <= N:
        ret = (ret + dfs(i+1, N // x)) % mod
    return ret

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

Submission status: Wrong Answer

Solution code:
N, K = (int(i) for i in input().split())
N += 1
l1 = []
l2 = []
n_ma = 0
for i in range(1, N):
    j = (N-1)//(i+1) + 1
    if i > j:
        break
    elif i == j:
        l1.append(i)
        break
    l1.append(i)
    l2.append(j)
l2.reverse()
L = l1 + l2 + [N]
M = len(L) - 1
DP = [[0] * (M+1) for counter1 in range(K+1)]

def BIT_query(BIT, idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(BIT, idx, x):
    while idx <= M:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def BIT_debug(BIT):
    return [BIT_query(BIT, i) - BIT_query(BIT, i-1) for i in range(1, M+1)]

MOD = 10**9 + 7
for i in range(M):
    BIT_update(DP[1], i+1, L[i+1]-L[i])
for i in range(1, K):
    for j in range(M):
        x = BIT_query(DP[i], M-j)
        x *= L[j+1]-L[j]
        x %= MOD
        BIT_update(DP[i+1], j+1, x)

print(K, M)

print(BIT_query(DP[K], M)%MOD)

Submission status: Wrong Answer

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

L = [N]
c = 2
while c < N**0.5:
    if L[-1] != N//c:
        L.append(N//c)
    c += 1
if c > N**0.5:
    c -= 1
    L.append(c)
else:
    L.append(c)


L.reverse()
dp = [[0 for j in range(c+len(L))] for i in range(K+1)]

for j in range(1, c+1):
    dp[2][j] = N//j
for j in range(1, len(L)):
    dp[2][j+c] = N//L[j]*(L[j]-L[j-1])

for i in range(2, K):
    dp[i+1][1] = sum(dp[i])
    for j in range(2, c+len(L)):
        dp[i+1][j] = dp[i+1][j-1]-dp[i][len(dp[0])+1-j]
        if j > c:
            dp[i+1][j] *= (L[j-c]-L[j-c-1])
#    for j in range(1, len(L)):
#        dp[i+1][j+c] *= (L[j]-L[j-1])
        

print(sum(dp[K])%(10**9+7))

Submission status: Wrong Answer

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

L = [N]
c = 2
while c < N**0.5:
    if L[-1] != N//c:
        L.append(N//c)
    c += 1
if c > N**0.5:
    c -= 1
    L.append(c)
else:
    L.append(c)


L.reverse()
dp = [[0 for j in range(c+len(L))] for i in range(K+1)]
num = 0
for j in range(1, c+1):
    dp[2][j] = N//j
    num += dp[2][j]
for j in range(1, len(L)):
    dp[2][j+c] = N//L[j]*(L[j]-L[j-1])
    num += dp[2][j+c]

for i in range(2, K):
    dp[i+1][1] = num
    num = 0
    for j in range(2, c+len(L)):
        dp[i+1][j] = dp[i+1][j-1]-dp[i][len(dp[0])+1-j]
        num += dp[i+1][j]
    for j in range(1, len(L)):
        dp[i+1][j+c] *= (L[j]-L[j-1])
        num += dp[i+1][j+c]
        

print(sum(dp[K])%(10**9+7))

Submission status: Wrong Answer

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

L = []
c = 1
while c < N**0.5:
    if N%c == 0:
        L.append(N//c)
    c += 1
if c > N**0.5:
    c -= 1
    L.append(c)
else:
    L.append(c)


L.reverse()
dp = [[0 for j in range(c+len(L))] for i in range(K+1)]

for j in range(1, c+1):
    dp[2][j] = N//j
for j in range(1, len(L)):
    dp[2][j+c] = N//L[j]*(L[j]-L[j-1])

for i in range(2, K):
    dp[i+1][1] = sum(dp[i])
    for j in range(2, c+len(L)):
        dp[i+1][j] = dp[i+1][j-1]-dp[i][len(dp[0])+1-j]
    for j in range(1, len(L)):
        dp[i+1][j+c] *= (L[j]-L[j-1])
        

print(sum(dp[K])%(10**9+7))

Submission status: Wrong Answer

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

ans = 0
for i in range(1, N+1):
    print(N // i)
#    ans += (N // i) ** (K - 1)

print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(1, N+1):
    ans += (N // i) ** (K - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
md=10**9+7
n,k=map(int,input().split())
i=1
ws=[]
s=0
while 1:
    w=n//i-n//(i+1)
    if w==1:
        ws+=[1]*(n-s)
        break
    ws.append(w)
    s+=w
    i+=1
m=len(ws)
dp0=ws[::-1]
dp1=[0]*m
#print(ws)
#print()
for _ in range(k-1):
    s=0
    for j in range(m):
        s+=dp0[j]
        dp1[m-j-1]=(s*ws[j])%md
    dp0=dp1[:]
#    print(dp0)
print(sum(dp0)%md)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
md=10**9+7
a=[]
pre=n
cnt=0
dp0=[]
for i in range(1,n+1):
    j=n//i
    if j==pre:
        cnt+=1
    elif j==1:
        a.append(cnt)
        dp0.append(pre*cnt)
        a.append(n+1-i)
        dp0.append(n+1-i)
        break
    else:
        a.append(cnt)
        dp0.append(pre*cnt)
        cnt=1
        pre=j
m=len(a)
a=a[::-1]
dp0=dp0[::-1]
#print(a)
#print(dp0)
dp1 = [0] * m
for _ in range(k-2):
    s=0
#    dp1=[0]*m
    for i,a1 in enumerate(a):
       s+=dp0[m-1-i]
       dp1[i]=s*a1
#    print(dp1)
    dp0=dp1[:]
#print(dp0)
print(sum(dp0))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
md=10**9+7
a=[]
pre=n
cnt=0
for i in range(1,n+1):
    j=n//i
    if j==pre:
        cnt+=1
    elif j==1:
        a.append([pre,cnt])
        a.append([1,n+1-i])
        break
    else:
        a.append([pre,cnt])
        cnt=1
        pre=j
m=len(a)
a=a[::-1]
dp0=[a0*a1 for a0,a1 in a]
for _ in range(k-2):
    s=0
    dp1=[0]*m
    for i,(a0,a1) in enumerate(a):
       s+=dp0[m-1-i]
       dp1[i]=s*a1
    dp0=dp1
print(sum(dp0))

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
n,k=map(int,input().split())
s_n = int(n**.5)
t_upper=[] #ｔ＝n//jの種類を数えるのに使う、t>s_nのもの
t_lower=[]
t_cnt_upper=[]#tとなるjの個数
t_cnt_lower=[]

x = -1
former = -1
for i in range(1,s_n+1):
  if x!= -1:
    former = x
    t_cnt_upper.append(former - n//i)
  x = n//i
  t_lower.append(i)
  t_cnt_lower.append(1)
  t_upper.append(x)
if t_upper[-1] != t_lower[-1]:
  t_cnt_upper.append(former - x)
#print(t_lower,t_upper,t_cnt_lower,t_cnt_upper) 


l = len(t_cnt_upper)
t_cnt = t_cnt_lower
for i in range(l):
  x = t_cnt_upper.pop()
  t_cnt.append(x)
num_array = len(t_cnt)
#print(t_cnt)


dp = [0]*num_array
for i in range(num_array):
  dp[i] = t_cnt[i]
for i in range(k-1):
  prev_dp = dp
  s_prev_dp = [0]*num_array
  for j in range(num_array):
    if j == 0:
      s_prev_dp[j] = prev_dp[j]
    else:
      s_prev_dp[j] += s_prev_dp[j-1] + prev_dp[j]
  for j in range(num_array):
    dp[j] = (s_prev_dp[-1-j] * t_cnt[j])%MOD
#print(dp)
ans = sum(dp)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

MOD=10**9+7
n,k=map(int,input().split())
s_n = int(n**.5)
t_upper=np.array([],dtype='int64') #ｔ＝n//jの種類を数えるのに使う、t>s_nのもの
t_lower=np.array([],dtype='int64')
t_cnt_upper=np.array([],dtype='int64') #tとなるjの個数
t_cnt_lower=np.array([],dtype='int64')

x = -1
former = -1
for i in range(1,s_n+1):
  if x!= -1:
    former = x
    t_cnt_upper=np.append(t_cnt_upper,former - n//i)
  x = n//i
  t_lower = np.append(t_lower,i)
  t_cnt_lower= np.append(t_cnt_lower,1)
  t_upper = np.append(t_upper,x)
if t_upper[-1] != t_lower[-1]:
  t_cnt_upper=np.append(t_cnt_upper,former - x)
print(t_lower,t_upper,t_cnt_lower,t_cnt_upper) 


l = len(t_cnt_upper)
t_cnt = t_cnt_lower
for i in range(l):
  x = t_cnt_upper[-1]
  t_cnt_upper = np.delete(t_cnt_upper,-1)
  t_cnt = np.append(t_cnt,x)
num_array = len(t_cnt)
print(t_cnt)

dp = np.zeros(num_array,dtype='int64')
for i in range(num_array):
  dp[i] = t_cnt[i]
for i in range(k-1):
  prev_dp = dp
  s_prev_dp = prev_dp.cumsum()
  for j in range(num_array):
    dp[j] = (s_prev_dp[-1-j] * t_cnt[j])%MOD
#print(dp)
ans = dp.sum()%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

MOD=10**9+7
n,k=map(int,input().split())
t=np.array([],dtype='int64') #ｔ＝n//jの種類を数えるのに使う
t_cnt=np.array([],dtype='int64') #tとなるjの個数
#print(t,t_cnt)

for i in range(1,n+1):
  tmp=n//i
  if tmp not in t:
    t = np.append(t,tmp)
    t_cnt = np.append(t_cnt,1)
  else:
    t_cnt[-1]+=1
s = t_cnt.cumsum()
num_array = len(t)
#print(s)

dp = np.zeros(num_array,dtype='int64')
for i in range(num_array):
  dp[i] = t_cnt[i]
for i in range(k-1):
  prev_dp = dp
  s_prev_dp = prev_dp.cumsum()
  for j in range(num_array):
    dp[j] = s_prev_dp[-1-j] * t_cnt[j]
#print(dp)
ans = dp.sum()
print(ans)

Submission status: Wrong Answer

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

cnt = np.array([1 for _ in range(m)] + [n // i - n // (i + 1) for i in range(1, n // m)][::-1])
nxt = np.cumsum(cnt)[::-1]

for _ in range(k - 1):
	cnt = (cnt * nxt) % mod
print(sum(cnt))

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = list(map(int, input().split()))
n, k = 3, 2
mod = 10 ** 9 + 7
m = int(n ** 0.5)

cnt = np.array([1 for _ in range(m)] + [n // i - n // (i + 1) for i in range(1, n // m)][::-1])
nxt = np.cumsum(cnt)[::-1]

for _ in range(k - 1):
	cnt = (cnt * nxt) % mod
print(sum(cnt))

Submission status: Wrong Answer

Solution code:
def limit(last,N):
  return(int(N/last))

def loop(last,remain,N):
  su=0
  if remain==0:
    return(1)
  else:
    for i in range(int(N/last)):
      times=1
      for j in range(remain):
        times=times*loop(i+1,remain-1,N)
      su+=times
  return(su)


N,K=map(int,input().split())
ssu=loop(1,K-1,N)
print(ssu/1000000007)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
n,k=map(int,input().split())
t=[]#ｔ＝n//jの種類を数えるのに使う
t_cnt=[]#tとなるjの個数

for i in range(1,n+1):
  tmp=n//i
  if tmp not in t:
    t.append(tmp)
    t_cnt.append(1)
  else:
    t_cnt[-1]+=1
#print(t,t_cnt)

m = len(t)
ans = [[0]*m for i in range(k)]
s_ans = [0]*m #累積和用

for i in range(m):
  ans[0][i] = t_cnt[i]
for i in range(1,k):
  s_ans[0] = ans[i-1][0]
  for j in range(1,m):
    s_ans[j] = s_ans[j-1] + ans[i-1][j]
  #print(s_ans)
  for j in range(m):
    ans[i][j] = s_ans[-1-j] * t_cnt[j]
#print(ans)

x = 0
for i in range(m):
  x += ans[-1][i] % MOD
print(x)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
n,k=map(int,input().split())
t=[]#ｔ＝n//jの種類を数えるのに使う
t_cnt=[]#tとなるjの個数

for i in range(1,n+1):
  tmp=n//i
  if tmp not in t:
    t.append(tmp)
    t_cnt.append(1)
  else:
    t_cnt[-1]+=1
#print(t,t_cnt)

m = len(t)
ans = [[0]*m for i in range(k)]
s_ans = [0]*m #累積和用

for i in range(m):
  ans[0][i] = t_cnt[i]
for i in range(1,k):
  s_ans[0] = ans[i-1][0]
  for j in range(1,m):
    s_ans[j] = s_ans[j-1] + ans[i-1][j]
  #print(s_ans)
  for j in range(m):
    ans[i][j] = s_ans[-1-j] * t_cnt[j]
#print(ans)

x = 0
for i in range(m):
  x += ans[-1][i]%MOD
print(x)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
n,k=map(int,input().split())
t=[]#ｔ＝n//jの種類を数えるのに使う
t_cnt=[]#tとなるjの個数

for i in range(1,n+1):
  tmp=n//i
  if tmp not in t:
    t.append(tmp)
    t_cnt.append(1)
  else:
    t_cnt[-1]+=1
#print(t,t_cnt)

m = len(t)
ans = [[0]*m for i in range(k)]
s_ans = [0]*m #累積和用

for i in range(m):
  ans[0][i] = t_cnt[i]
for i in range(1,k):
  s_ans[0] = ans[i-1][0]
  for j in range(1,m):
    s_ans[j] = s_ans[j-1] + ans[i-1][j]
  #print(s_ans)
  for j in range(m):
    ans[i][j] = s_ans[-1-j] * t_cnt[j]
#print(ans)

x = 0
for i in range(m):
  x += ans[-1][i]
print(x)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, K):
    r = set([0])
    for i in range(1, math.ceil(math.sqrt(N))):
        r.add(N//i)
        r.add(i)
    r = list(r)
    r.sort()

    m = {}
    for i in range(len(r)-1):
        m[i+1] = r[i+1]-r[i]
    DP1 = {k: v for k, v in m.items()}
    DP2 = {}
    M = Mod(10**9+7)
    for _ in range(K):
        S = [0]
        for k in range(1, len(DP1)+1):
            S.append(M.add(S[-1], DP1[k]))
        for k in DP1:
            DP2[k] = M.mul(S[len(DP1)-k+1], m[k])
        DP1, DP2 = DP2, DP1

    ans = 0
    for v in DP2.values():
        ans = M.add(ans, v)
    return ans


def main():
    N, K = read_int_n()
    print(slv(N, K))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

SQN = int(N**0.5)
JN = [0]  # N//j table
j = 1
while j*j<N:
    if j not in JN:
        JN.append(j)
    if N//j not in JN:
        JN.append(N//j)
    j += 1

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: Wrong Answer

Solution code:
N,K=map(int,input().split())
if N==1:
    print(1)
    exit()
mod=10**9+7
Layer=[]
a=1
b=1
while(b<N):
    a=b
    b=N//(N//a)+1
    Layer.append((a,b))
#print(Layer)
num=[x[1]-x[0] for x in Layer]
M=len(Layer)
#print(num)
dp=[[0 for j in range(M+1)] for i in range(K+1)]
dp[0][0]=1
sdp=[0 for i in range(M+2)]
for k in range(K):
    for j in range(M+1):
        sdp[j+1]=(dp[k][j]+sdp[j])%mod
    for j in range(M):
        dp[k+1][j]=(sdp[M-j]*num[j])%mod
ans=0
for j in range(M+1):
    ans+=dp[K][j]
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
mod=10**9+7
Layer=[]
a=1
b=1
while(b<N):
    a=b
    b=N//(N//a)+1
    Layer.append((a,b))
#print(Layer)
num=[x[1]-x[0] for x in Layer]
M=len(Layer)
#print(num)
dp=[[0 for j in range(M+1)] for i in range(K+1)]
dp[0][0]=1
sdp=[0 for i in range(M+2)]
for k in range(K):
    for j in range(M+1):
        sdp[j+1]=(dp[k][j]+sdp[j])%mod
    for j in range(M):
        dp[k+1][j]=(sdp[M-j]*num[j])%mod
ans=0
for j in range(M+1):
    ans+=dp[K][j]
    ans%=mod
print(ans)

Submission status: Wrong Answer

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()
    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()