Problems
체스에서 rook은 가로, 세로 방향으로 어느 곳이나 한 번에 움직일 수 있다.
즉 다음과 같은 체스판에서 rook이 X 라고 표시된 위치에 있을 때,
그 다음 rook이 움직여 갈 수 있는 부분은 어둡게 칠해진 부분 중의 하나이다.
N × 1,000,000 크기의 체스판이 주어졌다.
체스판의 i번째 행에는 1열부터 W[i]열까지의 칸을 제외한 모든 칸에 장애물이 놓여있다.
우리는 거기에 K개의 rook을 배치하려고 하는데, 모든 rook들은 서로 잡아먹을 수 없어야 한다.
그렇다면 rook들을 어떻게 배치해야만 할까?
단, 장애물이 있는 곳에는 rook을 놓을 수가 없다.
장애물을 사이에 두고 rook을 배치하면 잡아먹을 수 없다.
가능한 모든 경우의 개수를 출력한다.
Input
첫 줄에 체스판의 가로 크기 N, rook의 수 K (1 ≤ N ≤ 500, 1 ≤ K ≤ 500)가 주어진다.
두 번째 줄에 체스판의 i번째 행의 크기 W[i] (1 ≤ W[i] ≤ 1,000,000)가 주어진다.
Output
체스판에서 K개의 rook들이 서로 잡아먹지 않는 위치로 놓을 수 있는 방법의 수를 출력한다.
앞선 N Rook 문제들보다 체스판의 크기가 커져서 정답이 엄청 커진 만큼, 정답을 1,000,000,007로 나눈 나머지를 출력한다.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 40 | 입력받은 모든 값(N, K, W[i])이 15 이하이다. |
| #2 | 30 | 입력받은 모든 값(N, K, W[i])이 100 이하이다. |
| #3 | 30 | 추가 제약 조건은 없다. |
Example #1
3 3
2 1 3
2
Example #2
4 1
1 2 3 4
10
Example #3
5 2
2 3 1 2 4
43
Example #4
3 2
999999 999999 999999
990979013
Tag
Source
COCI 2008/2009 Contest4 6
You must sign in to write code.