def update(i,v):
while i<M:
fen[i] += v
fen[i] %= mod
i += i&-i
def cal(i):
s = 0
while i:
s += fen[i]
s %= mod
i -= i&-i
return s
def solve():
arr = [0]*(N+1)
for i in idx:
arr[i] = cal(i)
update(i,count[i])
return arr
N,K = map(int,input().split()); M = 1<<17; mod = 10**9+7
seq = [*map(int,input().split())]
idx = [x[1] for x in sorted((seq[i],i+1) for i in range(N))]
count = [0]+[1]*N
for _ in range(K-1):
fen = [0]*M
count = solve()
print(sum(count)%mod)
팬윅트리+DP로 해결하였다.
기본적인 풀이 아이디어는 달리기 [백준 2517번] 달리기 (Python3) (tistory.com) 와 동일하다. 수열이 작은 인덱스부터 채우면서 앞쪽에 현재 숫자보다 작은 숫자가 몇 개 있는지를 확인하면 된다.
이때 현재 숫자에서 뒤에 존재하는 길이가 K인 부분수열은 현재 이전에 존재하는 길이 K-1의 부분수열의 합이라 할 수 있다. 따라서 이를 DP로 해결할 수 있다.
달리기 문제에서 약간의 추가 아이디어가 필요한 문제
오늘의 교훈) 팬윅트리는 유용하다.