레이팅 미적용늘 그렇듯, 소 베시는 농부 존의 헛간에서 말썽을 부리고 있다. FJ에게는 \(N\) (\(1\leq N \leq 5000\))개의 건초 더미 무더기가 있다. 각 \(i\in [1,N]\)에 대해, \(i\)번째 무더기에는 \(h_i\) (\(1\le h_i\le 10^9\))개의 건초 더미가 있다. 베시는 건초 더미가 무너지는 것을 원하지 않으므로, 그녀가 할 수 있는 연산은 다음뿐이다.
- 인접한 두 무더기의 높이 차가 정확히 1이면, 더 높은 무더기의 맨 위 건초 더미 하나를 더 낮은 무더기로 옮길 수 있다.
위 연산을 유한 번 수행한 후 얻을 수 있는 배치의 수를 \(10^9+7\)로 나눈 나머지는 얼마인가? 모든 \(i\)에 대해 \(i\)번째 무더기의 건초 더미 개수가 두 배치에서 같으면 두 배치는 같은 것으로 간주한다.
출제자: Daniel Zhang
배점
- 입력 1-3은 \(N\le 10\)을 만족한다.
- 입력 4는 모든 \(i\)에 대해 \(1\le h_i\le 3\)을 만족한다.
- 입력 5-7은 모든 \(i\)에 대해 \(|h_i-i|\le 1\)을 만족한다.
- 입력 8-10은 모든 \(i\)에 대해 \(1\le h_i\le 4\)이고 \(N\le 100\)을 만족한다.
- 입력 11-13은 \(N\le 100\)을 만족한다.
- 입력 14-17은 \(N\le 1000\)을 만족한다.
- 입력 18-21에는 추가 제약이 없다.
출제자: Daniel Zhang
첫째 줄에 독립적인 테스트 케이스의 수 \(T\) (\(1\le T\le 10\))가 주어지며, 하나의 입력을 올바르게 해결하려면 모든 테스트 케이스를 풀어야 한다.
각 테스트 케이스는 \(N\)과 그 뒤의 \(N\)개의 높이로 이루어진 수열로 구성된다. 모든 테스트 케이스에 대한 \(N\)의 합이 \(5000\)을 넘지 않음이 보장된다.
각 테스트 케이스마다 한 줄씩, 총 \(T\)개의 줄을 출력한다.
7
4
2 2 2 3
4
3 3 1 2
4
5 3 4 2
6
3 3 1 1 2 2
6
1 3 3 4 1 2
6
4 1 2 3 5 4
10
1 5 6 6 6 4 2 3 2 54
4
5
15
9
8
19For the first test case, the four possible configurations are:
$$ (2,2,2,3), (2,2,3,2), (2,3,2,2), (3,2,2,2). $$
For the second test case, the four possible configurations are:
$$ (2,3,3,1),(3,2,3,1),(3,3,2,1), (3,3,1,2). $$
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > January > Platinum