Problem:


Score : 600 points

Problem Statement

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

Constraints

1\leq N\leq 10^9

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

N and K are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

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

Sample Input 1

3 2

Sample Output 1

5

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

Sample Input 2

10 3

Sample Output 2

147

Sample Input 3

314159265 35

Sample Output 3

457397712



Sample input:
3 2


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
n, k = map(int, input().split())
MOD = 10**9 + 7
max1 = int(sqrt(n))
dp1 = [[0 for _ in range(max1+1)] for _ in range(k)]
for j in range(1, max1+1):
	dp1[0][j] = 1
max2 = int(n/(max1+1))
dp2 = [[0 for _ in range(max2+1)] for _ in range(k)]
for j in range(1, max2+1):
	dp2[0][j] = int(n/j) - int(n/(j+1))

for i in range(k-1):
	csum1 = (sum(dp1[i])+sum(dp2[i])) % MOD
	dp1[i+1][1] = csum1
	for j in range(2, max1+1):
		dp1[i+1][j] = (dp1[i+1][j-1] - dp2[i][j-1]) % MOD
	csum2 = sum(dp1[i][:max2+1]) % MOD
	dp2[i+1][max2] = (csum2*dp2[0][max2]) % MOD
	for j in range(max2-1, 0, -1):
		csum2 -= dp1[i][j+1]
		csum2 %= MOD
		dp2[i+1][j] = (csum2*dp2[0][j]) % MOD

print((sum(dp1[k-1])+sum(dp2[k-1]))%MOD)

Submission status: Time Limit Exceeded

Solution code:
def f_small_products(N, K, MOD=10**9 + 7):
    # 参考: https://atcoder.jp/contests/abc132/submissions/6187073
    sqrt_n = int(N**0.5)

    # num: 0 <= i <= Nについて、N // i の値で同一視できるものの個数が前から格納される
    num = [0 for i in range(2 * sqrt_n + 1)]
    # 1から√N までは、同一視できるものの個数は1つ
    for i in range(1, sqrt_n + 1):
        num[i] = 1
    # √NからN までは、複数の整数が同一視されることがある
    for i in range(1, sqrt_n + 1):
        lo = max(sqrt_n + 1, (N + i + 1) // (i + 1))
        hi = N // i
        num[2 * sqrt_n + 1 - i] = hi - lo + 1

    # dp[n][m]: 最後の整数が m であるような n 個の整数を
    # 並べて条件を満たすようにする場合の数
    dp = [[0 for j in range(2 * sqrt_n + 2)] for i in range(K + 1)]
    dp[0][1] = 1  # 数列の先頭のさらに1個前に1があるとみなす(置き方1通り)
    for i in range(K):
        # 累積和を用いたdpテーブルの更新(imos法)
        for j in range(1, 2 * sqrt_n + 1):
            ways = (dp[i][j] * num[j]) % MOD
            dp[i + 1][1] += ways
            dp[i + 1][2 * sqrt_n + 2 - j] -= ways
        for j in range(1, 2 * sqrt_n + 1):
            dp[i + 1][j] += dp[i + 1][j - 1]

    return sum(a * b for a, b in zip(dp[K], num)) % MOD

N, K = [int(i) for i in input().split()]
print(f_small_products(N, K))

Submission status: Time Limit Exceeded

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

M=[]
i=1
while i <= N:
    j = N // (N // i)
    M.append(j-i+1)
    i+=j-i+1
l=len(M)

mn=[0]*l
total=0
for i,m in enumerate(M):
    total+=m
    mn[i]+=total

mn1=[0]*l
for k in range(1,K):
    total=0
    for i,mni in enumerate(mn[::-1]):
        total+=mni* M[i]
        total%=1000000007
        mn1[i]=total
    mn,mn1=mn1,mn

print(mn[l-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7


def main():
  N, K = map(int, input().strip().split())
  dp = {}

  keys = []
  i = 1
  while i <= N:
    v = N // i
    j = N // v
    keys.append((v, j - i + 1))
    i += j - i + 1

  total = 0
  for nj, w in keys:
    total += w
    dp[nj] = total

  for i in range(2, K + 1):
    tmp = {}
    total = 0
    for nj, w in keys:
      j = N // nj
      v = dp[j] * w
      total += v
      total %= MOD
      tmp[nj] = total

    dp = tmp

  return dp[1]


if __name__ == '__main__':
  print(main())

Submission status: Time Limit Exceeded

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

l = rt*2-1 if rt*rt+rt>N else rt*2
m = [[0,0] for i in range(l)]
for i in range(rt):
    m[i][0]=i+1
    m[l-1-i][0]=math.floor(N/(i+1))
m[0][1]=1

for i in range(1,l):
    m[i][1]=m[i][0]-m[i-1][0]


mn=[m[i][1] for i in range(l)]
mn1=[0]*l
for k in range(1,K):
    y=0
    for i in range(0,l):
        y+=mn[i]
        mn1[l-1-i]=y*m[l-1-i][1]%1000000007
    mn,mn1=mn1,mn

print(sum(mn)%1000000007)

Submission status: Time Limit Exceeded

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

c = []
for i in range(1,int(N**0.5)+1):
    c.append(i)
    c.append(int(N/i))
c = list(set(c))
c.sort()

k = []
for i in c:
    if int(N/i) != int(N/(i+1)):
        k.append(i)

dp = [[0]*len(k) for _ in range(K)]
for i in range(len(k)):
    dp[0][i]=k[i]

inv = [0]*(len(k)-1)
for i in range(len(k)-1):
    inv[i] = pow(k[i+1]-k[i],mod-2,mod)

index = [0]*len(k)
for i in range(len(k)):
    m = int(N/(k[i]+1))
    index[i] = bisect(k,m)

for i in range(K-1):
    dp[i+1][0] = dp[i][-1]
    for j in range(len(k)-1):
        m = int(N/(k[j]+1))
        l = index[j]
        S = dp[i][l-1]+(dp[i][l]-dp[i][l-1])*(m-k[l-1])*inv[l-1]
        dp[i+1][j+1] = dp[i+1][j]+(k[j+1]-k[j])*S
        dp[i+1][j+1] %= mod

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

Submission status: Time Limit Exceeded

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

c = []
for i in range(1,int(N**0.5)+1):
    c.append(i)
    c.append(int(N/i))
c = list(set(c))
c.sort()

k = []
for i in c:
    if int(N/i) != int(N/(i+1)):
        k.append(i)

dp = [[0]*len(k) for _ in range(K)]
for i in range(len(k)):
    dp[0][i]=k[i]

def S(n,m):
    l = bisect(k,m)
    return dp[n][l-1]+(dp[n][l]-dp[n][l-1])*(m-k[l-1])*pow(k[l]-k[l-1],mod-2,mod)

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import math

MOD = 1000000007



def fact(n):
  ans = {0}
  for i in range(1,math.ceil(n**0.5)+1):
      ans.add(i)
      ans.add(n//i)
  return sorted(list(ans))

def main():
  N,K = map(int, input().split())
  dp = [{} for _ in range(K+1)]
  keys = fact(N)
  dp[1] = {f:f for f in keys}

  for i in range(1,K):
    j_prev = 0
    dp[i+1][0] = 0
    for j in keys[1:]:
      dp[i+1][j] = (dp[i+1][j_prev] + (j-j_prev)*dp[i][N//j]) % MOD
      j_prev = j
  print(dp[K][N])


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
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 = (cnt + [1 for _ in range(n - sum(cnt))])[::-1]
nxt = cnt[:]

for _ in range(k - 1):
	cnt = [sum([x * nxt[i] % mod for x in cnt[:(len(cnt) - i)]])  for i in range(len(cnt))]
print(sum(cnt) % mod)

Submission status: Time Limit Exceeded

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
      times=times*loop(i+1,remain-1,N)
      su+=times
  return(su)


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

Submission status: Time Limit Exceeded

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]

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]


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

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

    NDP2[0]+=NDP1[-1]

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


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

    DP1=NDP1
    DP2=NDP2
    DP1.pop()
    DP2.pop()

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

Submission status: Time Limit Exceeded

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]

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]


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

    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]


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

    DP1=NDP1
    DP2=NDP2
    DP1.pop()
    DP2.pop()

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

Submission status: Time Limit Exceeded

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

Solution code:
from math import floor

N, K = map(int, input().split())

MOD = 10**9 + 7


# floor(N / i) の値に応じてグループ分けし、
# グループ単位で条件を満たす列の個数を動的計画法で求める
P = floor(N**0.5)
Q = N // P
R = P + Q
C = [
    1 if i <= P else
    N // (R - i) - N // (R - i + 1)
    for i in range(R)
]

dp = [
    [0 for _ in range(R)]
    for _ in range(K)
]
for i in range(R):
    dp[0][i] = C[i]
for j in range(1, K):
    acc = 0
    for i in reversed(range(1, R)):
        acc = (acc + dp[j - 1][R - i]) % MOD
        dp[j][i] = (C[i] * acc) % MOD
ans = sum(dp[K - 1]) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import floor

N, K = map(int, input().split())

MOD = 10**9 + 7


# floor(N / i) の値に応じてグループ分けし、
# グループ単位で条件を満たす列の個数を動的計画法で求める
P = floor(N**0.5)
Q = N // P
C = (
    [1 for _ in range(P + 1)] +
    [
        N // (Q - i) - N // (Q - i + 1)
        for i in range(1, Q)
    ]
)

dp = [[0 for _ in range(P + Q)] for _ in range(K)]
dp[0] = [C[i] for i in range(P + Q)]
for j in range(1, K):
    acc = 0
    for i in range(P + Q - 1, 0, -1):
        acc = (acc + dp[j - 1][P + Q - i]) % MOD
        dp[j][i] = (C[i] * acc) % MOD
ans = sum(dp[K - 1]) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import floor

N, K = map(int, input().split())

MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


# floor(N / i) の値に応じてグループ分けし、
# グループ単位で条件を満たす列の個数を動的計画法で求める
P = floor(N**0.5)
Q = N // P

C = (
    [ModInt(1) for _ in range(P + 1)] +
    [
        ModInt(N // (Q - i) - N // (Q - i + 1))
        for i in range(1, Q)
    ]
)

dp = [[0 for _ in range(P + Q)] for _ in range(K)]
dp[0] = [C[i] for i in range(P + Q)]
for j in range(1, K):
    acc = 0
    for i in range(P + Q - 1, 0, -1):
        acc += dp[j - 1][P + Q - i]
        dp[j][i] = C[i] * acc

ans = sum(dp[K - 1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
def sub(k, n):
  if k==1:
    return N // n
  r = 0
  for i in range(1,(N//n)+1):
    r += sub(k-1, i)
  return r % 1000000007
print(sub(K, 1))

Submission status: Time Limit Exceeded

Solution code:
def main():
	N, K = map(int, input().split())
	DIV = 10**9+7
	sqrtn = int(N**0.5)
	ans = 1
	s = []
	for i in range(1, sqrtn+1):
		s.append(i)
		if i < N//i:
			s.append(N//i)
	s.sort()

	r = []
	for i in range(len(s)-1):
		left = N//s[i+1]
		right = N//s[i]
		r.append(right-left)
	r.append(1)

	m = len(s)
	mp = {}
	for i in range(m):
		mp[s[i]] = i

	dp = [[0 for _ in range(m)] for _ in range(K+1)]
	dp[0][mp[N]] = 1
	for i in range(K):
		for j in range(m-2, -1, -1):
			dp[i][j] += dp[i][j+1]
			dp[i][j] %= DIV
		for j in range(m):
			nj = mp[N//s[j]]
			dp[i+1][j] += dp[i][nj]*r[j]%DIV
			dp[i+1][j] %= DIV

	ans = 0
	for j in range(m):
		ans += dp[K][j]
		ans %= DIV
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    l = []
    sq = int(n ** 0.5) + 1
    for i in range(1,sq+1):
        l.append((i,n//i,1))

    t = sq
    # print(sq,l)
    for j,i,_ in l[::-1]:
        # print(j,i,_)
        if t >= i:
            continue
        c = i - t
        l.append((i,j,c))
        t = i

    # print(l)

    ll = len(l)
    dp = [0] * ll
    dp[0] = 1

    p = [(i,l[i][1],l[i][2]) for i in range(ll-1,-1,-1)]
    l.append((inf,0,0))
    o = [t[0] for t in l]
    for i in range(k):
        np = [0] * ll
        m = 0
        c = 0
        q = o[0]
        for j,t,tc in p:
            while q <= t:
                c += dp[m]
                m += 1
                q = o[m]
            np[j] = c * tc % mod
        dp = np

    # print(dp)
    return sum(dp) % mod


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    l = []
    sq = int(n ** 0.5) + 1
    for i in range(1,sq+1):
        l.append((i,n//i,1))

    t = sq
    # print(sq,l)
    for j,i,_ in l[::-1]:
        # print(j,i,_)
        if t >= i:
            continue
        c = i - t
        l.append((i,j,c))
        t = i

    # print(l)

    ll = len(l)
    dp = [[0] * ll for _ in range(k+1)]
    dp[0][0] = 1

    l.append((inf,0,0))
    for i in range(k):
        dpi = dp[i]
        np = dp[i+1]
        m = 0
        c = 0
        for j in range(ll-1,-1,-1):
            t = l[j][1]
            tc = l[j][2]
            while l[m][0] <= t:
                c += dpi[m]
                c %= mod
                m += 1
            np[j] = c * tc % mod

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


print(main())

Submission status: Time Limit Exceeded

Solution code:
Q = 10**9+7
from collections import deque
from itertools import accumulate
#import sys
#input = sys.stdin.readline
def main():
    N, K = map( int, input().split())
    ans = 0
    d = deque()
    e = deque()
    M = int(N**(1/2))*2
    for i in range(1, int(N**(1/2))+1):
        if i**2 == N:
            d.append(i)
            M -= 1
            continue
        d.append(i)
        e.appendleft(N//i)
    T = list(d)+list(e)
    CT = [1]*M
    for i in range(1,M):
        CT[i] = T[i] - T[i-1]
    accT = list( map(lambda x:x%Q, accumulate(CT) ))
    dp = [[0]*M for _ in range(K)]
    for i in range(M):
        dp[1][i] = accT[-i-1]*CT[i]%Q
    for k in range(1, K-1):
        accT[0] = dp[k][0]
        for i in range(M-1):
            accT[i+1] = (accT[i]+dp[k][i+1])%Q
        for i in range(M):
            dp[k+1][i] = accT[-i-1]*CT[i]%Q
    print(sum(dp[K-1])%Q)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


@lru_cache(maxsize=None)
def next_max(n):
    # ある数と隣り合わせになれる数
    return int(N // n)


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


@lru_cache(maxsize=None)
def rec(n, k):
    if n <= 0:
        return 0
    if k <= 1:
        return n

    i = next_max(n)
    p = NM[i] if i < len(NM) else 1
    ret = rec(i, k - 1) * p % MOD
    cum = rec(n - p, k)
    return (cum + ret) % MOD


cnt = N
nums = []
while cnt >= 1:
    nums.append(cnt)
    i = next_max(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 = next_max(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: Time Limit Exceeded

Solution code:
import math
import os
import sys
from functools import lru_cache

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


@lru_cache(maxsize=None)
def next_max(n):
    # ある数と隣り合わせになれる数
    return int(N // n)


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


# @lru_cache(maxsize=None)
# @debug
# def rec1(n, k):
#     if k <= 1:
#         return n
#
#     ret = 0
#     cnt = n
#     while cnt > 0:
#         i = next_max(cnt)
#         p = NM[i] if i < len(NM) else 1
#         ret = (ret + rec1(i, k - 1) * p) % MOD
#         cnt -= p
#     return ret
#
#
# #
# # ans = rec1(N, K)
# # print(ans % MOD)


@lru_cache(maxsize=None)
def rec(n, k):
    if n <= 0:
        return 0
    if k <= 1:
        return n

    i = next_max(n)
    p = NM[i] if i < len(NM) else 1
    ret = rec(i, k - 1)
    cum = rec(n - p, k)
    ret = ret * p % MOD
    return (cum + ret) % MOD


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

Submission status: Time Limit Exceeded

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.floor(math.sqrt(N))+1):
        r.add(N//i)
        r.add(i)
    r = list(r)
    r.sort()
    # print(r)

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

Solution code:
n,m=map(int,input().split(' '))
Mod=1000000007
spl=int(n**0.5)+1
f,k=[i for i in range(spl)]+[n//i for i in range(1,spl)][::-1],2*spl-1
dp=[0]+[1]*(k-1)
for i in range(m):
	dp2=[0]*k
	for j in range(1,k):
		dp2[j]=(dp2[j-1]+dp[k-j]*(f[j]-f[j-1]))%Mod
	dp=dp2
print(dp[k-1])

Submission status: Time Limit Exceeded

Solution code:
def BC132_F():
    n, k = list(map(int, input().split(' ')))
    mod = 10**9 + 7
    mem = {}

    def dp(s, l):
        if l == 2: return n // s
        if (s, l) in mem: return mem[(s, l)]
        mem[(s, l)] = sum([dp(x, l - 1) for x in range(1, n // s + 1)]) % mod
        return mem[(s, l)]

    return dp(1, k + 1)


print(BC132_F())

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
# As = [N//i for i in range(1,int(N**0.5)+1)]
# Bs = [As[i]-As[i+1] for i in range(len(As)-1)]
# Bs[0] -= 1
# Bs = sorted(Bs) + [1]
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)]


from itertools import accumulate
# print(As,nums)
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: Time Limit Exceeded

Solution code:
import numpy
n,k=map(int,input().split())
N=32768
M=1000000007
a=[min(i,n)for i in range(N)]
b=[0]+[n//i for i in range(1,N)]
for _ in range(k-1):
    c=[i%M for i in numpy.cumsum(b)]
    d=[a[i]*(n//i-n//(i+1)) for i in range(1,N-1)] + [c[n//(N-1)]]
    sm=sum(d)
    d=[0,sm%M] + [i%M for i in sm-numpy.cumsum(d)][:-1]
    a=c
    b=d
print(b[1])

Submission status: Time Limit Exceeded

Solution code:
import math
from bisect import bisect_left

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):
            v = N // mapping[j]
            idx = bisect_left(mapping, v)
            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: Time Limit Exceeded

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

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 29 22:14:02 2019

@author: Yamazaki Kenichi
"""

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

r = int(pow(N,1/2))

const = []
if N // r == r:
    s = r - 1
else:
    s = r

for i in range(1,r+1):
    const.append(N//i - N//(i+1))
#if r == int(pow(N,1/2)) :
#    const += [1]
const.reverse()
const = [1 for i in range(s)] + const

dp = [[]]
for c in const:
    try:
        dp[0].append(dp[0][-1] +c)
    except:
        dp[0].append(c)
dp += [[0 for i in range(len(const))] for k in range(K-1)]

for k in range(1,K):
    for i in range(len(const)):
        dp[k][i] = (dp[k][i-1] + dp[k-1][len(const)-i-1]%mod
                      * const[i])%mod
print(dp[-1][-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
P = 10**9+7
R = int(N**0.5)+1
A = [i for i in range(R)] + [N//i for i in range(1, R)][::-1]
M = len(A)
X = [0] + [1] * (M-1)
for i in range(1, K+1):
    NX = [0] * M
    for j in range(1, M):
        NX[j] = (NX[j-1] + X[M-j]*(A[j]-A[j-1])) % P
    X = NX
print(X[-1])

Submission status: Time Limit Exceeded

Solution code:
import math

mod = 10**9+7

N, K = map(int, input().split())

root_n = int(math.sqrt(N))

scale = [0 for _ in range(root_n * 2)]
last = N
for i in range(root_n+1):
    div = N // (i+1)
    if i <= div:
        scale[i] = 1
        if i != 0:
            scale[-i] = last-div
    last = div

# print(scale)
dp0 = scale[:]
dp1 = [None for _ in range(root_n * 2)]

for _ in range(K-1):
    sum_val = 0
    for i in range(root_n * 2):
        sum_val += dp0[i]
        dp1[root_n*2 -i-1] = sum_val * scale[root_n*2 -i-1] % mod

    dp0 = dp1[:]
    # print(dp0)

print(sum(dp0) % mod)

Submission status: Time Limit Exceeded

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)
memo = {(K, e): 1 for e in U}
for k in range(K-1, -1, -1):
    memo[k, 0] = 0
    r = 0
    for x, y in zip(U, U[1:]):
        memo[k, y] = r = ((y - x) * memo[k+1, N//y] + r) % MOD
print(memo[0, N])

Submission status: Time Limit Exceeded

Solution code:
import math

from itertools import accumulate

def cumsum(a):
    return list(accumulate(a))

n,k = map(int, input().split())
if n == 1:
    print(1)
    exit()
mod = 10 ** 9 + 7
now = n
big = []
for i in range(2,int(math.sqrt(n)+2)):
    d = n // i
    big.append(now - d)
    now = d
big.reverse()
l = [1] * d + big
l2 = [1] * d + big
for i in range(k-1):
    a = cumsum(l)
    a.reverse()
    count = 0
    for i,j in zip(a,l2):
        l[count] = (i * j) % mod
        count += 1
l = cumsum(l)
ans = l[-1] % mod
print(ans)

Submission status: Time Limit Exceeded

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

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


def re_count(n, i):
    # n は前の数値
    # i は後ろからカウント
    ans = 0
    if i == 1:
        return N // n
    for x in range(1, N // n+1):
        ans += re_count(x, i-1)
    return ans % mod

print(re_count(1, K))

Submission status: Time Limit Exceeded

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

import collections
pairs = collections.Counter()
for n in range(1, N +1):
    pairs[n] = N // n

ans = 0
for n in range(1, N+1):
    candidates = [pairs[n]]
    for _ in range(K-1):
        new_candidates  = []
        for c in candidates:
            for k in range(1, c+1):
                new_candidates.append(pairs[k])
        candidates = new_candidates
    ans += len(candidates)
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

ans_array = []
divide_max = N

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

for i in range(divide):
    ans_array.append(1)
ans_array = ans_array[::-1]
ans_count = copy.deepcopy(ans_array)
# 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(ans_length):
        ans_array[i] = ans_acc[ans_length-i-1] * ans_count[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: Time Limit Exceeded

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

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
    for i in range(k-1):
        if X[i]*X[i+1] > n:
            ans -= 1
            break

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