31538번 - 출근하기 싫어 2 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 22 | 14 | 13 | 65.000% |
문제
이 문제는 출근하기 싫어 1과 굵은 글씨로 적힌 부분과 제한 조건만 다릅니다.
누구나 그렇듯 동우는 출근하기 싫다. 그래도 출근해야 한다.
동우가 다니는 회사는 신기한 회사이다. 총 $N$명의 직원이 있는데, 이 중 최대 $2$명이 출근하지 않아도 업무를 정상적으로 진행할 수 있다. 하지만 $2$명보다 많이 출근하지 않으면 업무를 정상적으로 진행할 수 없다.
동우는 회사의 업무가 정상적으로 진행되는 것이 신기해 현재 시각으로부터 최근 $M$시간 동안 $N$명의 직원 각각이 총 몇 시간씩 출근했는지 살펴보았다.
직원들은 모두 정각에만 출근해 정각에만 퇴근하며, 한 사람이 여러 번 출근 혹은 퇴근할 수 있다. 최근 $M$시간 동안 업무를 계속 정상적으로 진행할 수 있도록 하는, $N$명의 직원이 출근한 조합의 경우의 수를 구하시오.
이때, $M$시간에 대해 매시 30분을 기준으로 출근해 있는 직원들의 목록이 한 번이라도 다른 경우 서로 다른 조합으로 간주한다. 현재는 정각이라 가정한다.
입력
첫 번째 줄에 직원의 수 $N$과 동우가 살펴본 최근 시간의 길이를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. $(1\le N, M\le 5\,000)$
두 번째 줄에 $N$명의 직원이 최근 $M$시간 동안 출근한 시간 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(0\le A_i \le M)$
출력
직원이 출근한 조합으로 가능한 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.
단, $10^9+7$은 소수이다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 22 | $N\times M \le 20$ |
| 2 | 51 | $N, M \le 100$ |
| 3 | 70 | $N, M \le 500$ |
| 4 | 107 | 추가적인 제한 조건 없음 |
예제 입력 1
2 4 3 3
예제 출력 1
16
예제 입력 2
3 4 4 3 3
예제 출력 2
16
예제 입력 3
3 5 1 1 2
예제 출력 3
0
예제 입력 4
2 4 2 2
예제 출력 4
36
예제 입력 5
3 5 4 3 4
예제 출력 5
230
예제 입력 6
3 5 3 3 3
예제 출력 6
690
예제 입력 7
2 10 5 7
예제 출력 7
30240
출처
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring F번
- 문제를 만든 사람: eoaud0108, kidw0124, sshs29hanul
- 문제를 번역한 사람: tikiliki0417
- 문제를 검수한 사람: tlsdydaud1, w8385, yijw0930
채점 및 기타 정보
- 예제는 채점하지 않는다.