증가 수열의 개수
면접 대비시간 제한1초메모리 제한512 MB
서로 다른 값을 가진 길이 N의 수열에서 길이가 K인 증가 부분수열의 개수를 1e9+7로 나눈 나머지로 구한다.
문제
크기가 N인 수열 A와 정수 K가 주어진다. A의 증가하는 부분 수열 중 길이가 K인 것의 개수를 구하자.
입력
첫째 줄에 N, K가 주어진다. 둘째 줄에 수열 A1, A2, ..., AN이 주어진다.
출력
첫째 줄에 A의 증가하는 부분 수열 중 길이가 K인 것의 개수를 109+7로 나눈 나머지를 출력한다.
제한
- 1 ≤ N ≤ 100,000
- 1 ≤ K ≤ 10
- 1 ≤ Ai ≤ N
- Ai는 모두 다른 수