20918번 - 좋은 배열 세기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 52 | 33 | 23 | 56.098% |
문제
Albert는 최근 재미있는 문제를 풀고 있다. 길이 n+1인 배열 A가 1부터 n-1까지의 정수를 한 번씩 포함하고, n을 두 번 포함하면 배열 A는 좋은 배열이다. 길이가 n+1인 좋은 배열의 개수는 정확히 (n+1)!/2 개 존재한다.
A가 길이 n+1인 좋은 배열이라면, Score(A) 는 다음과 같이 정의 된다: 1 ≤ i < j ≤ n+1 과 A[i] < A[j] 를 만족하는 쌍 (i, j)의 개수. 만약 A = [1, 2, 3, ..., n-1, n, n] 이라면 Score(A)는 (n+2)(n-1)/2로 최대가 되며, A = [n, n, n-1, n-2, ..., 2, 1] 이라면 Score(A) = 0으로 최소가 된다.
Albert는 n과 두 개의 정수 a, b 가 주어졌을 때, a ≤ Score(A) ≤ b 를 만족하는 길이 n+1인 좋은 배열의 개수를 세는 문제를 풀고 싶다. 예를 들어, n = 3, a = 2, b = 3 이라 하자. 총 12개의 좋은 배열 중 a ≤ Score(A) ≤ b를 만족하는 길이 4인 좋은 배열의 개수는 6개이다.
- A = [1, 2, 3, 3]: Score(A) = 5
- A = [1, 3, 2, 3]: Score(A) = 4
- A = [1, 3, 3, 2]: Score(A) = 3 (만족)
- A = [2, 1, 3, 3]: Score(A) = 4
- A = [2, 3, 1, 3]: Score(A) = 3 (만족)
- A = [2, 3, 3, 1]: Score(A) = 2 (만족)
- A = [3, 1, 2, 3]: Score(A) = 3 (만족)
- A = [3, 1, 3, 2]: Score(A) = 2 (만족)
- A = [3, 2, 1, 3]: Score(A) = 2 (만족)
- A = [3, 2, 3, 1]: Score(A) = 1
- A = [3, 3, 1, 2]: Score(A) = 1
- A = [3, 3, 2, 1]: Score(A) = 0
입력으로 n, a, b 가 주어졌을 때, a ≤ Score(A) ≤ b 를 만족하는 길이 n+1인 좋은 배열 A의 개수를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 한 줄에 n, a, b 가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 한 줄에 출력한다.
단, 답이 매우 클 수 있으므로 정답을 109+7 (= 1,000,000,007) 로 나눈 값을 출력한다.
제한
- 1 ≤ T ≤ 10,000
- 2 ≤ n ≤ 1,000
- 0 ≤ a ≤ b ≤ 1,000
예제 입력 1
5 3 2 3 4 0 1 4 4 5 8 10 20 12 0 77
예제 출력 1
6 4 22 123924 113510379
케이스 1: 본문에서 다루었다.
케이스 2: 다음 4개의 배열이 조건을 만족한다: [4, 4, 3, 2, 1], [4, 4, 3, 1, 2], [4, 4, 2, 3, 1], [4, 3, 4, 2, 1]
케이스 3: 추가 설명 없음
케이스 4: 추가 설명 없음
케이스 5: 모든 길이 13인 좋은 배열이 조건을 만족하므로 답은 3113510400 이지만 10^9+7로 나눈 나머지는 113510379 이다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호