RiseOJ – 열차 추적 2

설명

매일 급행 열차가 농장 옆을 지나간다. 열차에는 $$N$$ 개의 객차가 있으며 ( $1 \leq N \leq 10^5$ ), 각 객차에는 $$1$$ 이상 $$10^9$$ 이하의 양의 정수 라벨이 붙어 있다. 서로 다른 객차가 같은 라벨을 가질 수도 있다.

평소에 베시는 열차가 지나가는 것을 지켜보며 객차의 라벨을 추적한다. 하지만 오늘은 안개가 너무 짙어서 베시는 라벨을 하나도 볼 수 없다! 다행히도 베시는 도시의 믿을 만한 소식통으로부터 객차 라벨 수열의 슬라이딩 윈도우 최솟값들을 입수했다. 구체적으로, 베시는 양의 정수 $$K$$ 와 $$N-K+1$$ 개의 양의 정수 $c_1,\dots,c_{N+1-K}$ 를 알고 있는데, 여기서 $$c_i$$ 는 객차 $i, i+1, \dots, i+K-1$ 중 최소 라벨이다.

슬라이딩 윈도우 최솟값들과 모순되지 않게 각 객차에 라벨을 배정하는 방법의 수를 구해 베시를 도와주자. 이 수는 매우 클 수 있으므로, $$10^9 + 7$$ 로 나눈 나머지를 구하면 베시는 만족할 것이다.

베시의 정보는 완전히 신뢰할 수 있다. 즉, 모순되지 않는 라벨 배정 방법이 적어도 하나 존재함이 보장된다.

문제 제공: Dhruv Rohatgi

제약

문제 제공: Dhruv Rohatgi

입력 형식

첫째 줄에 공백으로 구분된 두 정수 $$N$$ 과 $$K$$ 가 주어진다. 이어지는 줄들에 슬라이딩 윈도우 최솟값 $c_1,\dots,c_{N+1-K}$ 가 한 줄에 하나씩 주어진다.

출력 형식

하나의 정수를 출력한다: 각 $1 \leq i \leq N-K+1$ 에 대해 객차 $i, i+1, \dots, i+K-1$ 중 최소 라벨이 $$c_i$$ 가 되도록, 각 객차에 $$10^9$$ 이하의 양의 정수를 배정하는 방법의 수를 $$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:

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

예제 1

입력

출력

문제 정보

riseoj 작성

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

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

태그

JudgeUSACO

열차 추적 2

평가 및 의견

풀이 제출