RiseOJ – 비내림차순 부분 수열

설명

베시는 최근 USACO 대회에 참가했다가 다음 문제를 만났다. 물론 베시는 푸는 법을 안다. 그런데 당신은 어떤가?

$1\ldots K$ $(1\le K\le 20)$ 범위의 정수만으로 이루어진 길이 $$N$$ $(1\le N\le 5\cdot 10^4)$ 의 수열 $A_1,A_2,\ldots,A_N$ 을 생각하자. $$[L_i,R_i]$$ $(1\le L_i\le R_i\le N)$ 형태의 쿼리 $$Q$$ 개( $1\le Q\le 2\cdot 10^5$ )가 주어진다. 각 쿼리에 대해, $A_{L_i},A_{L_i+1}\ldots, A_{R_i}$ 의 비내림차순 부분 수열의 개수를 $$10^9+7$$ 로 나눈 나머지를 계산하여라.

$A_L,\ldots,A_R$ 의 비내림차순 부분 수열이란 $$L\le j_1이고 \(A_{j_1}\le A_{j_2}\le \cdots \le A_{j_x}$인 인덱스 모음 $(j_1,j_2,\ldots, j_x)$를 말한다. 빈 부분 수열도 반드시 고려해야 한다!$

문제 제공: Benjamin Qi

제약

점수 배점

테스트 케이스 2-3은 $N\le 1000$ 을 만족한다.
테스트 케이스 4-6은 $K\le 5$ 을 만족한다.
테스트 케이스 7-9는 $Q\le 10^5$ 을 만족한다.
테스트 케이스 10-12는 추가 제약이 없다.

문제 제공: Benjamin Qi

입력 형식

첫째 줄에 공백으로 구분된 두 정수 $$N$$ 과 $$K$$ 가 주어진다.

둘째 줄에 공백으로 구분된 $$N$$ 개의 정수 $A_1,A_2,\ldots, A_N$ 이 주어진다.

셋째 줄에 정수 $$Q$$ 가 주어진다.

다음 $$Q$$ 개의 줄에는 각각 공백으로 구분된 두 정수 $$L_i$$ 와 $$R_i$$ 가 주어진다.

출력 형식

각 쿼리 $$[L_i,R_i]$$ 에 대해, $A_{L_i},A_{L_i+1}\ldots, A_{R_i}$ 의 비내림차순 부분 수열의 개수를 $$10^9+7$$ 로 나눈 나머지를 한 줄에 하나씩 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 nondec.in · 출력을 쓸 파일 nondec.out

예제 1

입력

출력

3
4
20

설명

For the first query, the non-decreasing subsequences are $$(), (2),$$ and $$(3).$$
$$(2,3)$$ is not a non-decreasing subsequence because
$A_2\not \le A_3.$

For the second query, the non-decreasing subsequences are $$()$$ , $$(4)$$ , $$(5)$$ ,
and $$(4,5)$$ .

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > January > Platinum

올림피아드 > USACO > 2019-2020 > January > Platinum

태그

JudgeUSACO

비내림차순 부분 수열

평가 및 의견

풀이 제출