Problem:


Score : 600 points

Problem Statement

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

Constraints

1\leq N\leq 10^9

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

N and K are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

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

Sample Input 1

3 2

Sample Output 1

5

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

Sample Input 2

10 3

Sample Output 2

147

Sample Input 3

314159265 35

Sample Output 3

457397712



Sample input:
3 2


Sample output:
5

Submission status: Accepted

Solution code:
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]) % mod if i != 0 else D[i] for i, d in enumerate(D)]
    dp = [0] * len(D)
    S = [D] + [[0] * len(D) for k in range(K - 1)]
    I = [bisect.bisect_left(D, N // d) for d in D]

    for k in range(1, K):
        for i in range(len(D)):
            j = I[i]
            dp[i] = (S[k - 1][j] * C[i]) % mod
            S[k][i] = (S[k][i - 1] + dp[i]) % mod
    print(S[-1][-1] % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

MOD = 10 ** 9 + 7
N, K = lr()
M = int(N**.5)

# M+1以上で、Nを割るとxになるもの
upper_cnt = np.zeros(M+1, dtype=np.int64) # 1-indexed
A = np.arange(M+1, dtype=np.int64)
upper_cnt[1:] = N // A[1:] - np.maximum(M, N // (A[1:]+1)) # Mの時はlowerで数えるので0に

# 桁DP
lower = np.zeros(M+1, dtype=np.int64) # 1-indexed
upper = np.zeros(M+1, dtype=np.int64)
#最初は制限なしなので1を置いておく
lower[1] = 1
for i in range(K):
    prev_lower = lower.copy()
    prev_upper = upper.copy()
    lower_cum = prev_lower.cumsum() % MOD
    upper_cum = prev_upper.cumsum() % MOD
    # lower と upper から lower へ
    lower = np.zeros(M+1, dtype=np.int64)
    lower[1:] += (lower_cum[-1] + upper_cum[-1])
    lower[1:] -= upper_cum[:-1] # 大きすぎる値を引く
    # upper から upper はなし
    # lower から upper へ
    upper = lower_cum * upper_cnt
    lower %= MOD; upper %= MOD

answer = (lower[1:].sum() + upper[1:].sum()) % MOD
print(answer)

Submission status: Accepted

Solution code:
def main():
    import sys
    from math import sqrt
    input = sys.stdin.readline

    mod = 1000000007
    N, K = map(int, input().split())
    n = int(sqrt(N))
    dp = [[0] * (2*n+1) for _ in range(K+1)]
    dp[0][1] = 1

    num = [0] * (n+1)
    for i in range(1, n):
        num[i] = N // i - N // (i+1)
    num[n] = N // n - n

    for i in range(K):
        cs = dp[i][:n+1]
        cs2 = dp[i][n+1:]
        for j in range(1, n+1):
            cs[j] = (cs[j] + cs[j-1])%mod
        for j in range(1, n):
            cs2[j] = (cs2[j] + cs2[j-1])%mod
        for j in range(1, n+1):
            dp[i+1][-j] = (cs[j] * num[j])%mod
            dp[i+1][j] = (cs2[-j] + cs[n])%mod
    ans = 0
    for a in dp[-1]:
        ans = (ans + a)%mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
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(len(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 = len(t) - j - 1
    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
    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: Accepted

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(BIT_query(DP[K], M)%MOD)

Submission status: Accepted

Solution code:
import math

n, k = map(int, input().split())
mod = 1000000007
n1 = int(math.sqrt(n))
if n1 * n1 == n:
    n2 = n1 - 1
else:
    n2 = n1

num = [n]
for i in range(1, n2):
    num.append(n // (i + 1))
    num[i - 1] -= num[i]
num[-1] -= n1

dp1 = [1      for i in range(n1)]
dp2 = [num[i] for i in range(n2)]
for _ in range(k - 1):
    l = sum(dp1) % mod
    newdp1 = [l for i in range(n1)]
    newdp2 = [0 for i in range(n2)]

    dp1sum = 0
    for j in range(0, n2):
        dp1sum = (dp1sum + dp1[j]) % mod
        newdp2[j] = (newdp2[j] + dp1sum * num[j]) % mod

    dp2sum = 0
    for j in range(n2 - 1, -1, -1):
        dp2sum = (dp2sum + dp2[j]) % mod
        newdp1[j] = (newdp1[j] + dp2sum) % mod
    dp1 = newdp1
    dp2 = newdp2
print((sum(dp1) + sum(dp2)) % mod)

Submission status: Accepted

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
x = int(n**0.5)
mod = 10**9+7
if x*(x+1)<=n:
  flg = 1
else:
  flg = 0
t = 2*x+flg
dp = [[0 for i in range(t)] for j in range(2)]
for i in range(1,t):
  if i<=x:
    dp[0][i] = 1
    dp[1][i] = 1
  else:
    p = t-i
    dp[0][i] = n//p-n//(p+1)
    dp[1][i] = n//p-n//(p+1)
dp[1] = list(accumulate(dp[1]))
for i in range(2,k+1):
  dp[1][1:] = dp[1][t:0:-1]
  for j in range(1,t):
    dp[1][j] = dp[1][j]*dp[0][j]%mod
  for j in range(1,t):
    dp[1][j] = (dp[1][j]+dp[1][j-1])%mod
print(dp[1][t-1])

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int,input().split())
MOD = 10**9+7
div = list(range(1, int(np.sqrt(N))+1))
L1 = len(div)
div2 = [N//val for val in div]
div2.sort()
if div[-1] == div2[0]:
    div2.remove(div2[0])
L2 = len(div2)
L = L1+L2
ls = [1]*L1 + [0]*L2
tmp = div[-1]
for i,val in enumerate(div2):
    ls[i+L1] = val-tmp
    tmp = val
dp = [0]*L
dp = np.zeros((L), dtype='int64')
ls = np.array(ls, dtype='int64')
dp[:] = ls
r = np.zeros(L+1, dtype='int64')
r[:-1] = np.cumsum(dp, dtype='int64')[::-1]
for i in range(K-1):
    dp = (r[:-1]*ls)%MOD
    r[:-1] = np.cumsum(dp, dtype='int64')[::-1]
print(r[0]%MOD)

Submission status: Accepted

Solution code:

"""
右におけるのが同じやつなら同一で扱う
普通なら√N * √Nになっちゃう


"""

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

lis = []
lis2 = []

i = 1
while i ** 2 <= N:

    if N // i != i:
        lis.append(i)
        lis2.append(N // i)
    else:
        lis.append(i)

    i += 1

lis2.reverse()
lis += lis2


dp = [0] * len(lis)

for i in range(len(lis)):
    if i == 0:
        dp[i] = 1
    else:
        dp[i] = lis[i]-lis[i-1]

#print (dp)

for loop in range(K):

    ndp = [0] * len(lis)
    nsum = 0
    
    for i in range((len(lis))):

        nsum += dp[i]
        nsum %= mod

        if i != len(lis)-1:
            ndp[-1-i] += ((lis[-1-i] - lis[-2-i]) * nsum) % mod
        else:
            ndp[-1-i] += nsum % mod

    dp = ndp

print (dp[0])

Submission status: Accepted

Solution code:
from numpy import int_

mod = 10 ** 9 + 7

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

M = int(N ** 0.5)

T = [N // i - N // (i + 1) for i in range(1, M + 1)]
A = int_([1] * (N - sum(T)) + T[::-1])

dp = A[:]
for _ in range(K - 1):
    dp = A * dp.cumsum()[::-1] % mod

print(dp.sum() % mod)

Submission status: Accepted

Solution code:
from numpy import int_

mod = 10 ** 9 + 7

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

M = int(N ** 0.5)

T = [N // i - N // (i + 1) for i in range(1, M + 1)]
A = int_([1] * (N - sum(T)) + T[::-1])

dp = A[:]
for _ in range(K - 1):
    dp = A * dp.cumsum()[::-1] % mod

print(sum(dp) % mod)

Submission status: Accepted

Solution code:
from numpy import int_

mod = 10 ** 9 + 7

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

M = int(N ** 0.5)
T = [N // i - N // (i + 1) for i in range(1, M + 1)]
dp = int_([1] * (N - sum(T)) + T[::-1])

A = dp[:]
for _ in range(K - 1):
    dp = A * dp.cumsum()[::-1] % mod

print(sum(dp) % mod)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


ans=0

n,k=LI()
b=[]

for i in range(1,int(n**0.5)+1):
    b+=[n//i]
    b+=[n//(n//i)]

b=sorted(set(b))
d=[i-j for i,j in zip(b,[0]+b)]
k+=1

m=len(b)
dp=[[0]*(m) for j in range(1+k)]
dp[0][0]=1

for i in range(k):
    sdp=[0]
    #show('dp',dp[i])
    for j in range(m):
        sdp.append((sdp[-1]+dp[i][j]*d[j])%mo)
    sdp=sdp[::-1]
    #show('sdp',sdp)
    for j in range(m):
        dp[i+1][j]=sdp[j]

print(sdp[0])

Submission status: Accepted

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

data=[i for i in range(1,int(n**.5)+1)]+[n//i for i in range(int(n**.5),0,-1)]

L=len(data)
dp=[1]*L
for i in range(1,L):
    dp[i]=data[i]-data[i-1]

for i in range(k-1):
    h=dp[:]
    for i in range(1,L):
        h[i]=(h[i]+h[i-1])%mod
    h=h[::-1]
    for i in range(1,L):
        h[i]=h[i]*(data[i]-data[i-1])%mod
    dp=h

ans=0
for u in dp:
    ans=(ans+u)%mod
print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7
p = int(n**0.5)


a = [i for i in range(1, p+1)]

for x in range(p, 0, -1):
    if n // x != p:
        a.append(n // x)

dp = [[0 for _ in range(len(a))] for _ in range(k)]

m = len(a)

temp = 0
b = [0] * m
for i, x in enumerate(a):
    b[i] = x - temp
    temp = x

for i in range(m):
    dp[0][i] = b[i]

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

#print(dp)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    # power_funcを用いて(nCk) mod p を求める 
    # nCk = n!/((n-k)!k!)を使用

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    # a^b mod p を求める
    # bを2進数分解して高速累乗

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

#D
def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge, g):

    dist = defaultdict(lambda: inf)
    dist[(start,0)] = 0
    q = [(dist[(start,0)], start, 0)]
    while q:
        du, u, t = heappop(q)
        for j in edge[u]:
            if t == 2:
                t = -1
            if dist[(j, t + 1)] > du + 1:
                dist[(j, t + 1)] = du + 1
                heappush(q, [dist[(j, t + 1)], j, t + 1])
    return dist
#E
def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = defaultdict(list)
    for x,y in v:
        edge[x].append(y)
    d = dijkstra(n, s, edge, t)
    if d[(t,0)] == inf:
        print(-1)
    else:
        print(d[(t,0)]//3)
    return

# F
# 解説AC
# √nまでで約数の全列挙ができるということは
# n <= a * b (a <= bとしたときに)
# 各 a は √nまでしかないことはわかる
# ( a > √n なら b < √n だからね)
# すると各aに対して対応するbの最大値が存在するため
# b の個数は高々 √n 個しか無いことがわかる
# 後はDPでどうぞ 
def F():
    n, k = LI()
    f = defaultdict(int)
    Range = int(sqrt(n))
    dp = [0] * (2 * Range)
    m = 0
    l = 0
    for i in range(Range, 0, -1):
        dp[i - 1] = 1
        f[i - 1] = 1
        if n // i == i:
            l = 1
            continue
        dp[Range + m] = n // i - n // (i + 1)
        f[Range + m] = n // i - n // (i + 1)
        m += 1
    R = 2 * Range - l
    for _ in range(k - 1):
        ndp = [0] * (2 * Range)
        for j in range(R):
            ndp[R - j - 1] = dp[j]
        ndp = list(itertools.accumulate(ndp[::-1]))[::-1]
        dp = [(d * f[num]) % mod for num,d in enumerate(ndp)]
    ans = sum(dp)%mod
    print(ans)
    return



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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter, defaultdict
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import copy
import bisect
MOD = 10**9 + 7
from logging import getLogger, StreamHandler, DEBUG, WARNING
logger = getLogger(__name__)
handler = StreamHandler()
handler.setLevel(DEBUG)
logger.setLevel(DEBUG)
# handler.setLevel(WARNING)
# logger.setLevel(WARNING)
logger.addHandler(handler)
def main():
    n,k = getList()

    # =================約数列挙=================
    divisors = []
    tmp_div = n + 1
    for i in range(1, int(math.sqrt(n)) + 3):
        if tmp_div * i > n:
            other = n // i
            if i > other:
                break
            elif i == other:
                divisors.append(i)
                break
            else:
                divisors.append(i)
                divisors.append(other)

    divisors.sort()
    n_div = len(divisors)
    # =================約数列挙=================

    # =================dp[0]の作成=============
    diff = [divisors[0]]
    for i, j in zip(divisors, divisors[1:]):
        diff.append(j - i)
    dp = copy.copy(diff)
    # print(dp)
    # =================dp[0]の作成=============

    for iteration in range(k-1):
        dp_copy = []
        tmp = sum(dp) % MOD
        dp_copy.append((tmp * diff[0]) % MOD)
        for cid, dp_content in enumerate(range(n_div - 1)):
            tmp -= dp[n_div - dp_content - 1]
            dp_copy.append((tmp * diff[cid+1]) % MOD)

        dp = copy.copy(dp_copy)

        # print(dp)
    print(sum(dp) % MOD)
    # print(acc)
    # print(n_div)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
mod = 10**9+7
n = int(N**0.5)
dp1 = [[0]*(n+1) for _ in range(K)]
dp2 = [[0]*(n+1) for _ in range(K)]
for i in range(1, n+1):
    dp1[0][i] = 1
dp2[0][n] = N//n-n
for i in range(1, n):
    dp2[0][i] = (N//i-N//(i+1))%mod
for i in range(1, K):
    cum = 0
    for j in range(1, n+1):
        dp2[i][j] = ((dp1[i-1][j]+cum)%mod*dp2[0][j])%mod
        cum+=dp1[i-1][j]
        cum%=mod
    for j in range(1, n+1)[::-1]:
        dp1[i][j] = (cum+dp2[i-1][j])%mod
        cum+=dp2[i-1][j]
        cum%=mod
print((sum(dp1[-1])%mod+sum(dp2[-1])%mod)%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    s=set()
    for i in range(1,1+int(n**.5)):
        s.add(i)
        s.add(n//i)
    A=sorted(s)
    m=len(A)
    coef=[0]*m
    coef[0]=1
    for i in range(1,m):
        coef[i]=A[i]-A[i-1]
    dp=[0]*m
    dp[0]=1
    for i in range(k):
        for j in range(m-1):
            dp[j+1]+=dp[j]
            dp[j+1]%=MOD
        ndp=[0]*m
        for j in range(m):
            ndp[j]=dp[m-j-1]*coef[j]
            ndp[j]%=MOD
        dp=ndp
    print(sum(dp)%MOD)
resolve()

Submission status: Accepted

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()

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

rootN = int(N**0.5)
num_list = [1]*rootN

now = rootN
for num in range(rootN, 0, -1):
	x = N//num
	num_list.append(x - now)
	now = x

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


mod = 10**9 + 7
for k in range(1, K):
	sum_before = [dp[k - 1][0]]
	for i in range(1, len(num_list)):
		sum_before.append(sum_before[-1]+dp[k - 1][i])
	for i in range(len(num_list)):
		dp[k][i] = (num_list[i]*sum_before[len(num_list) - 1 - i])%mod

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

Submission status: Accepted

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, n // sqt)][::-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: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

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

M = int(N**.5)

lower = np.zeros(M+1,np.int64)
upper = np.zeros(M+1,np.int64)
size = np.zeros(M+1,np.int64)
x = N//np.arange(1,M+1)
size[1:] = x; size[1:-1] -= x[1:]; size[M] = N//M - M

# 最初は1をひとつ持っておく
lower[1] += 1
for _ in range(K):
    prev_lower = lower
    prev_upper = upper
    prev_lower_cum = lower.cumsum() % MOD
    prev_upper_cum = upper[::-1].cumsum()[::-1] % MOD # 逆から累積しておく
    lower = np.zeros(M+1,np.int64)
    upper = np.zeros(M+1,np.int64)
    # 下→上
    upper += prev_lower_cum * size
    # 下→下
    lower[1:M+1] += prev_lower_cum[-1]
    # 上→下
    lower[1:M+1] += prev_upper_cum[1:M+1]
    lower %= MOD
    upper %= MOD

answer = (lower.sum() + upper.sum()) % MOD
print(answer)

Submission status: Accepted

Solution code:
from itertools import accumulate

N,K = map(int, input().split())
mod = 10**9+7
sqt = int(N**0.5)
cnt = [N // i-N // (i+1) for i in range(1, N//sqt)] + [1]*sqt
x = cnt
for _ in range(K):
    x = [(i*j)%mod for i, j in zip(accumulate(reversed(x)), cnt)]
    

print(x[-1])

Submission status: Accepted

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()
tsl = []
tsr = []
num = {}
for i in range(1, int(N ** 0.5) + 1):
    x = N // i
    y = N // (N // i)
    if not tsl or tsl[-1] > x:
        tsl.append(x)
    if x != y and (not tsr or tsr[-1] < y):
        tsr.append(y)
    if x not in num:
        num[x] = 0
    if y not in num:
        num[y] = 0
ts = tsl + tsr[::-1]

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


MOD = 1000000007
for i in range(1, K - 1):
    pref = 0
    for j in reversed(range(len(ts))):
        # R = idx[N // ts[j]]
        R = len(ts) - j - 1
        pref += dp[i-1][R]
        dp[i][j] = pref * num[ts[j]] % MOD
        # 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: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
P = 110000
MOD = 10 ** 9 + 7
S = [0] * P
dp = [[0] * P for i in range(110)]
num = [0] * P
i = 1
t = 0
while i <= N:
    j = N // i
    if i <= j:
        num[t] = 1
        t += 1
        i += 1
    else:
        num[t] = N // j - i + 1
        i = N // j + 1
        t += 1


dp[0][0] = 1
for k in range(K):
    S = [0] * P
    for j in range(t + 1):
        S[j + 1] = S[j] + dp[k][j]
        S[j + 1] %= MOD
    for j in range(t):
        dp[k + 1][j] = S[t - j] * num[j]
        dp[k + 1][j] %= MOD

ans = 0
for i in range(t + 1):
    ans += dp[K][i]
    ans %= MOD
print(ans)

Submission status: Accepted

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

# dp[i][x] := i文字目まで。最後がxとなるもの
# → O(10**11) で入らないので ルートN に圧縮する
rN = int(N ** 0.5)
T = {N//x for x in range(1, rN+1)}
T |= {x for x in range(1, rN+1)}
T = [0,] + sorted(list(T))	# 1-indexed

# 1-indexed
dp = []
dp.append([0,] + [T[i]-T[i-1] for i in range(1, len(T))])

for k in range(K-1):
	dp.append([0,] * len(T))
	dp[-1][-1] = dp[-2][1]
	for t in range(2, len(T)):
		dp[-1][-t] = (dp[-2][t] + dp[-1][-t+1]) % MOD
	for t in range(len(T)):
		dp[-1][t] = (dp[-1][t] * dp[0][t]) % MOD

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

Submission status: Accepted

Solution code:
from itertools import accumulate

MOD = 10**9 + 7

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

def N2sqrtN(N):
    M = int(N**0.5)
    As = list(range(1, M+1))
    Bs = [N//A for A in reversed(As)]
    if As[-1] == Bs[0]:
        return As + Bs[1:]
    else:
        return As + Bs

Bs = N2sqrtN(N)
lenB = len(Bs)

nums = [1]
for i in range(lenB-1):
    nums.append(Bs[i+1]-Bs[i])

dp = [0] * lenB
dp[0] = 1
for i in range(1, K+1):
    dp = list(accumulate(dp))
    dp = [dpi*num%MOD for dpi, num in zip(reversed(dp), nums)]

print(sum(dp) % MOD)

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import accumulate

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

MOD = 10**9 + 7
N, K = inpl()

p = 0
X = []
for i in range(1, int(sqrt(N))+1):
    X.append(N//i)

A = [1]*len(X) 
B = [X[-2-i] - X[-1-i] for i in range(len(X)-1)]
if sum(A) + sum(B) < N:
    C = A + [N-sum(A)-sum(B)] + B
else:
    C = A + B

DP = [c%MOD for c in C]

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

    for i in range(len(C)):
        DP2[i] = (S[-1-i]*C[i])%MOD

    DP = DP2

print(sum(DP)%MOD)

Submission status: Accepted

Solution code:
import math
from itertools import chain

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

modulo = 10 ** 9 + 7
sqrtN  = int(math.sqrt(N))

P = [N // d for d in range(1, sqrtN + 1)]

# M[i] - 正の整数k個を並べたもののうち, 先頭がiで,
#        隣接する整数の積がN以下のものの個数 (mod modulo).

# k == 1 のときは M[i] == 1
M = {i: 1 for i in chain(P, range(1, P[-1]))}

# M2[i] - M[i] at k
# M2[i] = sum(M[j] for j such that 1 <= j <= N // i)
#       = M2[m] + sum(M[j] for j such that N//m < j <= N//i) (some m > i)
for k in range(2, K + 2):
    M2 = {}
    M2[N] = M[1]
    for m, i in zip(P, P[1:]):
        M2[i]  = M2[m] + sum(M[j] for j in range(N // m + 1, N // i + 1))
        M2[i] %= modulo
    for i in range(P[-1] - 1, 0, -1):
        M2[i]  = M2[i + 1] + M[N // i] * (N // i - N // (i + 1))
        M2[i] %= modulo
    M = M2

print(M[1])

Submission status: Accepted

Solution code:
import numpy as np
N, K = tuple(map(int, input().split()))
mod = 1000000007

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

print(sum(cnt) % mod)

Submission status: Accepted

Solution code:
import numpy as np
N, K = list(map(int, input().split()))
mod = 1000000007

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

print(sum(cnt) % mod)

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
mod = 1000000007

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

print(sum(cnt) % mod)

Submission status: Accepted

Solution code:
from itertools import accumulate

def f(n,k):
    lim = int((n + 0.1) ** 0.5) + 1
    ws = []
    s = 0
    for i in range(1, lim):
        w = n // i - n // (i + 1)
        ws.append(w)
        s += w
    ws += [1] * (n - s)
    dp=ws
    m = len(ws)
    for _ in range(k - 1):
        dp=[s*w%md for s,w in zip(accumulate(dp[::-1]),ws)]
    print(sum(dp) % md)
md=10**9+7
n,k=map(int,input().split())
f(n,k)

Submission status: Accepted

Solution code:
def f(n,k):
    lim = int((n + 0.1) ** 0.5) + 1
    ws = []
    s = 0
    for i in range(1, lim):
        w = n // i - n // (i + 1)
        ws.append(w)
        s += w
    ws += [1] * (n - s)
    m = len(ws)
    dp0 = ws[::-1]
    dp1 = [0] * m
    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(sum(dp0) % md)
md=10**9+7
n,k=map(int,input().split())
f(n,k)

Submission status: Accepted

Solution code:
MOD = pow(10, 9) + 7

def main():
  n, k = map(int, input().split())
  dyaku = set([1, n])
  i = 2
  while i*i<=n:
    if n // i not in dyaku:
      dyaku.add(i)
      dyaku.add(n//i)
    i += 1
  reyaku = [0] + list(sorted(dyaku))
  ddyaku = {s: i+1 for i, s in enumerate(sorted(dyaku))}
  dp = [[0 for _ in range(k)] for _ in range(len(dyaku) + 1)]
  for i in range(1, len(dyaku)+1):
    dp[i][1] = (((reyaku[i] - reyaku[i-1]) * (n // reyaku[i])) % MOD + dp[i-1][1]) % MOD
  for i in range(2, k):
    for j in range(1, len(dyaku)+1):
      dp[j][i] = (((reyaku[j] - reyaku[j-1]) * dp[ddyaku[n//reyaku[j]]][i-1]) % MOD + dp[j-1][i]) % MOD
  print(dp[-1][-1])


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


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

  l = len(W)
  dp = [0] * l

  total = 0
  for i, w in enumerate(W):
    total += w
    dp[l - i - 1] = total

  for i in range(2, K + 1):
    tmp = [0] * l
    total = 0
    for j, w in enumerate(W):
      v = dp[j] * w
      total += v
      total %= MOD
      tmp[l - j - 1] = total

    dp = tmp

  return dp[0]


if __name__ == '__main__':
  N, K = map(int, input().strip().split())
  # import time
  # t = time.time()
  print(main(N, K))
  # print(time.time() - t)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
mod = 10 ** 9 + 7
sqrt = int(N**(1/2))
count = [N//i - N//(i+1) for i in range(1, N//sqrt)] + [1] * sqrt
ansList = count
for _ in range(K):
    ansList = [(i * j) % mod for i, j in zip(accumulate(reversed(ansList)), count)]

print(ansList[-1])

Submission status: Accepted

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