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

Solution code:
def cnt(n):
    #a<b
    #ab>a*a
    resequal=0
    resneq=0
    a=1
    while(a*a<=n):
        resequal+=1
        resneq+=(n//a)-a
        a+=1
    return resequal+2*resneq
def cnsum(n):
    #a<b
    #ab>a*a
    resequal=0
    resneq=0
    a=1
    while(a*a<=n):
        resequal+=a*a
        resneq+=((n//a)-a)*a*a
        resneq+=((n//a)*(1+n//a)*(1+2*(n//a)))//6
        resneq-=(a*(a+1)*(1+2*a))//6

        a+=1
    return resequal+resneq

mod=10**9+7
N,K=map(int,input().split())
X=cnt(N)%mod
Y=cnsum(N)%mod
def inv(x):
    return pow(x,mod-2,mod)
Expect=(Y*inv(X))%mod
ans=(X*pow(Expect,K-2,mod))%mod
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
MOD = 10**9 + 7
num = int(n**(0.5))
dp = [[0]*(num*2 + 1) for i in range(k+1)]

ruiseki = [i for i in range(num+1)]
ruiseki2 = [num-i for i in range(num+1)]
for i in range(k):
    for j in range(num):
        dp[i+1][j] = ruiseki[num] + ruiseki2[num - j]
    for j in range(num):
        dp[i+1][j+num] = ruiseki[num - j]
        dp[i][j] %= MOD
  
    ruiseki = [0]*(num+1)
    for j in range(num):
        ruiseki[j+1] = ruiseki[j] + dp[i+1][j]
        ruiseki[j+1] %= MOD

    ruiseki2 = [0]*(num+1)
    for j in range(num):
        ruiseki2[j+1] = ruiseki2[j] + dp[i+1][j + num]
        ruiseki2[j+1] %= MOD
        
print((sum(dp[k-1])*2 + k) % MOD)

Submission status: Wrong Answer

Solution code:
def f(tail, left):
  m = (tail, left)
  if m in memo:
    return memo[m]
  
  if left == 1:
    ret = n // tail
    memo[m] = n // tail
    return ret
  #if left == 0:
  #  return 1

  count = 0
  for i in range(n // tail):
    t = i + 1
    count += f(t, left - 1)
    #print("f({}, {})".format(t, left - 1))
  memo[m] = count
  return count

memo = {}

n, k = [int(v) for v in input().split()]
print(f(1, k))

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
P = 10**9 + 7

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

Submission status: Wrong Answer

Solution code:
hoge = input().split()
N = int(hoge[0])
K = int(hoge[1])

if K == 2:
  print(int((N*K-1) % (1e9 + 7)))
else:
  hage = round(N / 2 - 0.5 + 0.01)
  print(int((pow(K,K) * hage + (hage-1)*K) % (1e9 + 7)))

Submission status: Wrong Answer

Solution code:
import itertools
n, k = [int(i) for i in input().split()]
temp = [i for i in range(1, 101)]
temp2 = list(itertools.product(temp, repeat=2))
count = 0
print(len(temp2))
for i in range(len(temp2)):
	if temp2[i][0]*temp2[i][1] <= n:
		count += 1
print(count % (10**9+7))

Submission status: Wrong Answer

Solution code:
n,k = list(map(int,input().split(" ")))

def check(l,n):
    global k
    if len(l) > k:
        return False
    for i in range(len(l)):
        if i+1 == len(l):
            break
        if l[i] * l[i+1] > n:
            return False
    return True
a = 0
old_l = [1 for i in range(k)]
for i in range(0,k-1):
    for j in range(0,k):
        l = None
        l = old_l.copy()
        try:
            while check(l,n):
                l[i+j] += 1
                a += 1
                print(l)
        except:
            pass
print(a)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
# gcd
from fractions import gcd
# 切り上げ，切り捨て
from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
from collections import Counter, defaultdict
import math
from functools import reduce
# input関係の定義
# fin = open('in_3.txt', 'r')
# sys.stdin = fin
#
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


MOD = 1000000007  # type: int


def solve(N: int, K: int):
    d = defaultdict(int)
    for i in range(1, int(math.sqrt(N)) + 1):
        d[i] = N // i - N // (i + 1)
    for i in range(1, int(math.sqrt(N)) + 1):
        d[N // i] = 1
    # print(d)
    ans = 0
    for num, value in d.items():
        ans += value * pow(num, K - 1, MOD)
    print(ans % 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
    solve(N, K)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

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


m = int(n**0.5)
if m**2 < n:
    m += 1


dp = [[0]*(m+1) for i in range(k+1)]

for i in range(1,m):
    dp[1][i] = 1
dp[1][m] = n-m+1


for i in range(1,k):
    for j in range(1,m+1):
        r = n//j
        for p in range(1,r+1):
            p = min(p,m)
            dp[i+1][p] += dp[i][j]
            dp[i+1][p] %= mod

res = 0
for i in range(1,m+1):
    res = (res+dp[k][i])%mod
print(res)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
import itertools
li = (0,1,2,3,4,5,6,7,8,9)
li2 = list(itertools.permutations(li,k))

a = 0
s = 1
for i in range(len(li2)):
    for j in range(len(li2[i])-1):
        s =li2[i][j]*li2[i][j+1]
        if s<=n:
            a+=1
            s=0
print(a)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())

from itertools import product

ans = 0
for X in product(range(1,n+1), repeat=k):
    _ans = [1 if X[i]*X[i+1] > n else 0 for i in range(k-1)]
    if sum(_ans) == 0:
        print(X)
        ans += 1
    # for i in range(k-1):
    #     if X[i]*X[i+1] > n:
    #         ans -= 1
    #         break

print(ans % (10**9+7))

Submission status: Wrong Answer

Solution code:
import math
import sys
import io

sys.stdin = io.StringIO(
    """314159265 35"""
)

# ======================================================================

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: Time Limit Exceeded

Solution code:
def guchoku(n,k,mod):
    dp=[1]*(n+1)
    dp[0]=0
    for _ in range(k-1):
        ndp=[0]*(n+1)
        for i in range(1,n+1):
            ndp[i]+=sum([dp[j+1] for j in range(n//i)])
            ndp[i]%=mod
        dp=ndp.copy()
    return sum(dp)%mod
def main(n,k,mod):
    ary=[]
    tmp=0
    for i in range(1,int(n**0.5)+1):
        ary.append(n//i-n//(i+1))
        tmp+=ary[-1]
    tmp=n-tmp
    ary+=[1]*tmp
    ary.reverse()
    dp=[x for x in ary]
    m=len(ary)
    for i in range(m-1):
        dp[i+1]+=dp[i]
        dp[i+1]%=mod
    for _ in range(k-1):
        ndp=[0]*m
        for i in range(m):
            ndp[i]+=dp[-i-1]*ary[i]
            ndp[i]%=mod
            pass
        for i in range(m-1):
            ndp[i+1]+=ndp[i]
            ndp[i+1]%=mod
        dp=[x for x in ndp]
    return dp[-1]

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from math import sqrt
MOD = 10**9 + 7

def main():
    lim, n = map(int, input().split())
    num, tmp = [], []
    for i in range(1, int(sqrt(lim))+1):
        num.append(i)
        if i**2 != lim:
            tmp.append(lim//i)
    while len(tmp) > 0:
        num.append(tmp.pop(-1))
    m = len(num)
    dp = [[0]*m for _ in range(n)]
    dp[0][0] = 1
    for j in range(1, m):
        dp[0][j] = num[j] - num[j-1]
    for i in range(1, n):
        for j in range(1, m):
            dp[i-1][j] += dp[i-1][j-1]
        for j in range(m):
            idx = bisect_left(num, lim//num[j])
            p = num[j]
            if j > 0:
                p -= num[j-1]
            dp[i][j] = dp[i-1][idx] * p % MOD
    print(sum(dp[-1])%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
N,K = map(int,input().split())
M = int(N**0.5)
dp = [[0]*M for _ in range(K+1)]
dp1 = [[0]*M for _ in range(K+1)]
dp2 = [[0]*M for _ in range(K+1)]

dp[0][0] = 1
dp1[0][0] = 1
dp2[0][0] = N
for m in range(1,M):
    dp[0][m] = 1
    dp1[0][m] = dp1[0][m-1]+dp[0][m]
    dp2[0][m] += dp2[0][m-1]+N//(m+1)*dp[0][m]

dp[1][0] = N
dp1[1][0] = N
dp2[1][0] = N**2
for m in range(1,M):
    dp[1][m] = N//(m+1)
    dp1[1][m] = dp1[1][m-1]+dp[1][m]
    dp2[1][m] += dp2[1][m-1]+N//(m+1)*dp[1][m]


for k in range(1,K):
    for m in range(M):
        dp[k+1][m] = dp1[k][M-1]+N//(m+1)*dp1[k-1][m]+dp2[k-1][M-1]-dp2[k-1][m]-M*dp1[k-1][M-1]
        dp[k+1][m] %= mod
        dp1[k+1][m] = dp1[k+1][m-1]+dp[k+1][m]
        dp1[k+1][m] %= mod
        dp2[k+1][m] = dp2[k+1][m-1]+N//(m+1)*dp[k+1][m]
        dp2[k+1][m] %= mod

print(dp[K][0])

Submission status: Time Limit Exceeded

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

state= [] # 同じ状態とみなしてよいものの個数の配列
i = 1
while i <= N:
    if i*i <= N:
        state.append(1)
        i += 1
    else:
        j = N // i # iの後における最大の数
        state.append(N//j-i+1) 
        i = N//j + 1

L = len(state)
#print(state)

# dp[k][x] : 最後が状態xであるようなk個の整数を並べる場合の数
dp = [[0]*L for _ in range(K+1)]
dp[0][0] = 1

#dp[k+1][x] = sum_{y: xを後ろにおける状態} dp[k][y]
for k in range(K):
    cum_sum = [0] * (L+1)
    for y in range(L): 
        cum_sum[y+1] = (cum_sum[y] + dp[k][y]) % MOD

    for x in range(L):
        # xを後ろにおけるような最大の状態はL-x-1
        dp[k+1][x] += cum_sum[L-x]
        dp[k+1][x] *= state[x]
        dp[k+1][x] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = map(int, input().split())
MOD = 1000000007
i, A, B = 1, [], []
while i * i <= N:
  A.append(1)
  B.append(N // i - N // (i + 1))
  i += 1
B = list(reversed(B))
if sum(A) + sum(B) == N:
  C = (A+B)[::-1]
else:
  C = (A+B[1:])[::-1]
DP = C
L = len(C)
for k in range(K-1):
  DP = DP[::-1]
  DP[0] %= MOD
  for i in range(L-1):
    DP[i+1] += DP[i]
    DP[i+1] %= MOD
  for i in range(L):
    DP[i] = DP[i] * C[i] % MOD
print(sum(DP) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = map(int, input().split())
MOD = 1000000007
i, A, B = 1, [], []
while i * i <= N:
  A.append(1)
  B.append(N // i - N // (i + 1))
  i += 1
B = list(reversed(B))
if sum(A) + sum(B) == N:
  C = list(reversed(A + B))
else:
  C = list(reversed(A + B[1:]))
DP = C
L = len(C)
for k in range(K-1):
  DP = list(reversed(DP))
  DP[0] %= MOD
  for i in range(L-1):
    DP[i+1] += DP[i]
    DP[i+1] %= MOD
  for i in range(L):
    DP[i] = DP[i] * C[i] % MOD
print(sum(DP) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
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 = [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)

Submission status: Time Limit Exceeded

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]
    dp[i][j]=coef[j]*tmp
    dp[i][j]%=mod
print(sum(dp[k])%mod)

Submission status: Time Limit Exceeded

Solution code:
memo = {}

def dfs(i, ub):
    if i == K:
        return 1
    if (i, ub) in memo:
        return memo[(i, ub)]
    ret = 0
    x = 1
    while x <= ub and x * x <= N:
        ret = (ret + dfs(i+1, N // x)) % mod
        x += 1
    y = 1
    while y < N // y:
        cnt = min(N // y, ub) - min(N // (y + 1), ub)
        ret = (ret + cnt * dfs(i+1, y)) % mod
        y += 1
    memo[(i, ub)] = ret
    return ret

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

Submission status: Time Limit Exceeded

Solution code:
memo = {}

def dfs(i, ub):
    if (i, ub) in memo:
        return memo[(i, ub)]
    if i == K:
        return 1
    ret = 0
    x = 1
    while x <= ub:
        ret = (ret + dfs(i+1, N // x)) % mod
        x += 1
    memo[(i, ub)] = ret
    return ret

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - (m.i if isinstance(m, mint) else (m % MOD))
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        return mint(pow(i, m, MOD))
    def __truediv__(self, m):
        return mint(self.i * pow(m, MOD - 2, MOD) % MOD)
    def __repr__(self):
        return repr(self.i)


n, k = map(int, input().split())

l, r = 1, n + 1
while r - l > 1:
    c = (l + r) // 2
    if c ** 2 <= n:
        l = c
    else:
        r = c
r = l # less than or equal to sqrt(n)
# 1 ... r - 1, r, (r, n/r], ... (n/3, n/2], (n/2, n]
# (a, b] ... count for each elem in (a, b], not sum
# (r, n/r] is ignored if r*r == n
dp = [mint(0) for _ in range(2 * r)]
dp[0] = mint(1)
for _ in range(k):
    ndp = [mint(0) for _ in range(2 * r)]
    for i in range(1, r + 1):
        pre_cnt = dp[i - 1]
        if i == r and r ** 2 == n:
            ndp[r - 1] += pre_cnt
        else:
            ndp[-i] += pre_cnt
    for i in range(1, r + 1):
        if i == r and r ** 2 == n:
            continue
        pre_cnt = dp[-i]
        upper = n // i
        lower = r + 1 if i == r else 1 + n // (i + 1)
        ndp[i - 1] += pre_cnt * (upper - lower + 1)
    acc = mint(0)
    for i in range(r * 2 - 1, -1, -1):
        if i == r and r ** 2 == n:
            continue
        acc += ndp[i]
        dp[i] = acc

ans = mint(0)
for i in range(1, r + 1):
    ans += dp[i - 1]
for i in range(1, r + 1):
    upper = n // i
    lower = r + 1 if i == r else 1 + n // (i + 1)
    ans += dp[-i] * (upper - lower + 1)
print(ans)

Submission status: Time Limit Exceeded

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

num = []
now = N + 1
i = 1
while True:
  r = N // (i+1) + 1
  if r == now:
    break
  num.append(now - r)
  now = r
  i += 1
  
num += [1] * (N - sum(num))
n = len(num)
dp = [[0]*n for i in range(K)]
for _n in range(n):
  dp[0][_n] = num[_n]

for i in range(1, K):
  s = 0
  for _n in range(n):
    j = n - 1 - _n
    s += dp[i-1][j] % MOD
    s %= MOD
    dp[i][_n] = s * num[_n] % MOD

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq
import sys
import itertools
import queue


input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def P(N):
    D = []
    for n in range(1, int(N ** 0.5) + 1):
        D.append(n)
        if N // n != n:
            D.append(N // n)
    D.sort()
    return D


def main():
    N, K = read_values()
    D = P(N)
    C = [D[i] - D[i - 1] if i != 0 else D[i] for i, d in enumerate(D)]
    dp = {}
    SS = [[0] + D] + [[0] * (len(D) + 1) for k in range(K - 1)]

    for k in range(1, K):
        for i, d in enumerate(D):
            j = bisect.bisect_left(D, N // d)
            dp[d] = (SS[k - 1][j + 1] * C[i]) % mod
            SS[k][i + 1] = (SS[k][i] + dp[d]) % mod
    print(sum(dp.values()) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq
import sys
import itertools
import queue


input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def P(N):
    D = []
    for n in range(1, int(N ** 0.5) + 1):
        D.append(n)
        if N // n != n:
            D.append(N // n)
    D.sort()
    return D


def main():
    N, K = read_values()
    D = P(N)
    C = [D[i] - D[i - 1] if i != 0 else D[i] for i, d in enumerate(D)]
    dp = [{d: C[i] for i, d in enumerate(D)}] + [
        {d: 0 for d in D} for k in range(K - 1)
    ]
    SS = [[0] + [d for d in D]] + [[0] * (len(D) + 1) for k in range(K - 1)]
    for k in range(1, K):
        for i, d in enumerate(D):
            j = bisect.bisect_left(D, N // d)
            dp[k][d] = SS[k - 1][j + 1] * C[i]
            dp[k][d] %= mod
            SS[k][i + 1] = (SS[k][i] + dp[k][d]) % mod
    print(sum(dp[K - 1][d] for d in D) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def solve():
    m = 1
    a,b = [],[]
    while m*m <= N:
        a.append(m)
        b.append(N//m)
        m += 1
    if a[-1] == b[-1]:
        b.pop()
    a += b[::-1]
    w = [b-a for a,b in zip([0]+a, a)]
    
    L = len(a)
    dp = [1]*L
    for _ in range(K-1):
        dp2 = [0]*L
        c = 0
        for i,v in enumerate(w):
            c += dp[i] * v
            dp2[L-1-i] += c
            dp2[L-1-i] %= MOD
        dp = dp2
    return sum(a*b for a,b in zip(w,dp)) % MOD
print(solve())

Submission status: Time Limit Exceeded

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

m = 1
a,b = [],[]
while m*m <= N:
    a.append(m)
    b.append(N//m)
    m += 1
if a[-1] == b[-1]:
    b.pop()
a += b[::-1]
w = [b-a for a,b in zip([0]+a, a)]

L = len(a)
dp = [1]*L
for _ in range(K-1):
    dp2 = [0]*L
    c = 0
    for i,v in enumerate(w):
        c += dp[i] * v
        dp2[L-1-i] += c
        dp2[L-1-i] %= MOD
    dp = dp2
ans = sum(a*b for a,b in zip(w,dp))
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7
h = 1
t = set()
while h * h <= N:
  t.add(N // h)
  t.add(h)
  h += 1
t = sorted(t)
#print(t)
tt = []
for x in t:
  tt.append(N // x)

dp = [[0] * len(t) for _ in range(K + 1)]
dp[0][0] = 1
for i in range(K):
  for j in range(len(t)):
    k = bl(t, tt[j])
    dp[i + 1][k] += dp[i][j]
    dp[i + 1][k] %= mod
  #print(dp)
  for k in range(len(t) - 1, 0, -1):
    dp[i + 1][k - 1] += dp[i + 1][k]
    dp[i + 1][k - 1] %= mod
  for k in range(1, len(t)):
    rng = (t[k] - t[k - 1]) % mod
    dp[i + 1][k] *= rng
    dp[i + 1][k] %= mod
  #print(dp)
res = 0
#print(dp)
for j in range(len(t)):
  res += dp[-1][j]
  res %= mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7
h = 1
t = set()
while h * h <= N:
  t.add(N // h)
  t.add(h)
  h += 1
t = sorted(t)
#print(t)
tt = []
for x in t:
  tt.append(N // x)

dp = [[0] * len(t) for _ in range(K + 1)]
dp[0][0] = 1
for i in range(K):
  for j in range(len(t)):
    k = bl(t, tt[j])
    dp[i + 1][k] += dp[i][j]
    dp[i + 1][k] %= mod
  #print(dp)
  for k in range(len(t) - 1, 0, -1):
    dp[i + 1][k - 1] += dp[i + 1][k]
    dp[i + 1][k - 1] %= mod
  for k in range(1, len(t)):
    rng = t[k] - t[k - 1]
    dp[i + 1][k] *= rng
    dp[i + 1][k] %= mod
  #print(dp)
res = 0
#print(dp)
for j in range(len(t)):
  res += dp[-1][j]
  res %= mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from math import sqrt
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

M = int(sqrt(N))
i = 1
x = N
li1 = []
li2 = []
mul = []
while i < x:
    li1.append(x)
    i += 1
    prev = x
    x = N // i
    li2.append((prev - x) * (i - 1))
    mul.append(prev - x)
li = []
if i == x:
    li += li1 + [x] + li2[::-1]
else:
    li += li1 + li2[::-1]

M = len(li)
mul = [1] * (M-len(li2)) + mul[::-1]
dp = list2d(K-1, M, 0)
for i in range(M):
    dp[0][i] = li[i]

for i in range(1, K-1):
    acc = list(accumulate(dp[i-1]))[::-1]
    for j in range(M):
        dp[i][j] = acc[j] * mul[j] % MOD
print(sum(dp[K-2]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

n, k = map(int, input().split())
P = [[-1]*(k+1) for _ in range(n+1)]
MOD = 10**9+7

def product(l, k):
  if P[l][k] != -1:
    return P[l][k]
  if k==1:
    return l
  c = 0
  for i in range(1, l+1):
    c += product(n//i, k-1)
    c %= MOD
  P[l][k] = c
  return c

print(product(n, k))

Submission status: Time Limit Exceeded

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

n = 1
A = []
while True:
    A.append(N//n)
    if N//(n+1) < n+1: break
    n += 1
A.append(n)

L = 2*n
dp = [[0]*L for _ in range(K)]
for l in range(n):
    dp[0][l] = 1

i = 0
for l in reversed(range(n, L)):
    dp[0][l] = A[i] - A[i+1]
    i += 1

for k in range(1, K):
    s = 0
    for l in reversed(range(L)):
        s = (s+dp[k-1][L-l-1]) % mod
        dp[k][l] = s * dp[0][l] % mod

ans = 0
for l in range(L):
    ans = (ans + dp[K-1][l]) % mod

print(ans)

Submission status: Time Limit Exceeded

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

L = [N]

for i in range(2, int(N**0.5)+1):
    if L[-1] != N//i:
        L.append(N//i)
        
c = int(N**0.5)+1
if c > N**0.5:
    c -= 1
    L.append(c)
else:
    L.append(c)


L.reverse()
dp1 = [0 for _ in range(c+len(L))]
dp2 = [0 for _ in range(c+len(L))]

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

for i in range(2, K):
    if i%2 == 0:
        dp2[-1] = dp1[1]
        for j in range(2, c+len(L)):
            dp2[c+len(L)-j] = dp2[c+len(L)-j+1]+dp1[j]
        for j in range(1, len(L)):
            dp2[j+c] *= (L[j]-L[j-1])
    else:
        dp1[-1] = dp2[1]
        for j in range(2, c+len(L)):
            dp1[c+len(L)-j] = dp1[c+len(L)-j+1]+dp2[j]
        for j in range(1, len(L)):
            dp1[j+c] *= (L[j]-L[j-1])

if K%2 == 0:
    ans = sum(dp1)
else:
    ans = sum(dp2)

print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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()
dp1 = [0 for _ in range(c+len(L))]
dp2 = [0 for _ in range(c+len(L))]

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

for i in range(2, K):
    if i%2 == 0:
        dp2[-1] = dp1[1]
        for j in range(2, c+len(L)):
            dp2[c+len(L)-j] = dp2[c+len(L)-j+1]+dp1[j]
        for j in range(1, len(L)):
            dp2[j+c] *= (L[j]-L[j-1])
    else:
        dp1[-1] = dp2[1]
        for j in range(2, c+len(L)):
            dp1[c+len(L)-j] = dp1[c+len(L)-j+1]+dp2[j]
        for j in range(1, len(L)):
            dp1[j+c] *= (L[j]-L[j-1])

if K%2 == 0:
    ans = sum(dp1)
else:
    ans = sum(dp2)

print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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] = dp[i][1]
    for j in range(2, c+len(L)):
        dp[i+1][c+len(L)-j] = dp[i+1][c+len(L)-j+1]+dp[i][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: Time Limit Exceeded

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]
    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: Time Limit Exceeded

Solution code:
import sys

def solve():
    N, K = map(int, input().split())
    mod = 7 + 10 ** 9
    lim = 0
    for i in range(1, 10 ** 5):
        if i ** 2 > N:
            lim = i - 1
            break
    
    large = [0] * (lim + 1)
    for i in range(1, lim): large[i] = (N // i) - (N // (i + 1))
    large[lim] = N // lim - lim
   
    
    DP = [[0 for j in range(lim + 1)] for i in range(K)] #x <= lim
    DP[0] = [1] * (lim + 1)

    DPlarge = [[0 for j in range(lim + 1)] for i in range(K)] #x >= lim
    for i in range(1, lim+1): DPlarge[0][i] = large[i]

    for k in range(K-1):
        for i in range(1, lim + 1):
            for t in range(1, i + 1):
                DP[k+1][t] += DPlarge[k][i]
                DP[k+1][t] %= mod
                DP[k+1][t] += DP[k][i]
                DP[k+1][t] %= mod
            
            DPlarge[k+1][i] += (DP[k][i] * large[i]) % mod
            DPlarge[k+1][i] %= mod

            for t in range(i + 1, lim + 1):
                DPlarge[k+1][t] += (DP[k][i] * large[t]) % mod 
                DPlarge[k+1][t] %= mod
                DP[k+1][t] += DP[k][i]
                DP[k+1][t] %= mod
                

    ans = 0
    for i in range(1, lim+1):
        ans += (DP[K-1][i] + DPlarge[K-1][i]) % mod
        ans %= mod

    print(ans)
    #print(DP)
    #print(DPlarge)

    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

LIM = int(N ** 0.5) * 2 + 1
dp = [[0] * LIM for i in range(K - 1)]

ts = set()
num = {}
for i in range(1, int(N ** 0.5) + 1):
    x = N // i
    y = N // (N // i)
    ts.add(x)
    ts.add(y)
    if x not in num:
        num[x] = 0
    if y not in num:
        num[y] = 0

    # dp[0][idx[(N // ] += (N // i)
ts = sorted(ts, reverse=True)
idx = {k: i for i, k in enumerate(ts)}
for j, t in enumerate(ts):
    num[t] = (N // t - N // ts[j-1]) if j > 0 else 1
    # print(t, num[t])
    dp[0][idx[t]] = num[t] * t


for i in range(1, K - 1):
    pref = 0
    for j in reversed(range(len(ts))):
        R = idx[N // ts[j]]
        pref += dp[i-1][R]
        dp[i][j] = pref * num[ts[j]]
        # pref += dp[i-1][R] * num[ts[j]]

        # print(f"0 - {R}")
        # dp[i][j] = sum(dp[i-1][k] * num[ts[j]] for k in range(R + 1))
        # print(pref, dp[i][j])


# for x in dp:
    # print(x)
ans = sum(dp[-1])
print(ans % 1000000007)

Submission status: Time Limit Exceeded

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

mod = pow(10, 9)+7
def solve(pos, cur):
	if pos >= K:
		return 1
	total = 0

	i = 1
	while cur*i <= N:
		total += solve(pos+1, i)
		total %= mod
		i += 1
	return total
print(solve(0, 1))