배열 세기
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- COUNTARRAY
- 10000ms
- 131072kb
- 67
- 19 (28%)
-
- 출처
- 분류
문제
2014 개정수학 수II의 함수 단원을 공부하던 수찬이는 반복적인 학습이 지겨워서, 문제집에서 다루지 않는 함수를 만들기로 했다!
수찬이는 자신의 이니셜을 딴 \texttt{sc}(A, x)라는 함수를 만들기로 했다. A[1..n]는 길이가 n인 자연수(1 이상의 정수)로 구성된 배열이고, x는 자연수이다.
수찬이는 이 함수를 어떻게 정의하면 좋을지 고민하다가, 우연히 지학이를 만났다. 지학이는 배열에 아래와 같은 연산을 하며 놀고 있었다.
- 두 정수 l과 r (1 \le l \le r \le n)을 정한다.
- A[l], A[l+1], \cdots, A[r-1], A[r]에 각각 1을 더한다.
수찬이는 이 모습을 보고, \texttt{sc}(A, x)를 이렇게 정의하기로 했다.
- A[i] > x를 만족하는 i (1 \le i \le n)가 존재한다면 -1
- 존재하지 않는다면, A의 모든 원소를 x로 만들기 위해 지학이의 연산을 해야 하는 최소 횟수
수찬이는 함수를 정의한 기념으로, \texttt{sc}(A, k) = l를 만족하는 길이가 n인 서로 다른 배열 A가 몇 개나 되는지 세고자 한다. 그러나 수찬이가 직접 세기에는 이러한 경우의 수가 너무나 많았다.
수찬이를 도와 경우의 수가 몇 개인지 세어 보자.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
이후, 각 테스트 케이스마다 n, k, c (1 \le n \le 5000, 1 \le k \le 2000, 1 \le c \le 100)가 공백을 사이로 두고 한 줄에 주어진다.
출력
각 테스트 케이스마다 한 줄에 c+1개의 음이 아닌 정수를 출력한다. 이 중 (l+1)번째 수 (0 \le l \le c)는 \texttt{sc}(A, k) = l를 만족하는 배열 A의 개수를 1,000,000,009 (= 10^{9} + 9)로 나눈 나머지여야 한다.
예제 입력
1 3 2 3
예제 출력
1 6 1 0
노트
- \texttt{sc}(A, 2) = 0인 경우: [2, 2, 2]
- \texttt{sc}(A, 2) = 1인 경우: [1, 1, 1], [1, 1, 2], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 1]
- \texttt{sc}(A, 2) = 2인 경우: [1, 2, 1]
- \texttt{sc}(A, 2) = 3인 경우: 없음
어떤 두 배열 A[1..n]과 B[1..n]이 서로 다르다는 것은, A[i] \neq B[i] (1 \le i \le n)을 만족하는 i가 존재한다는 것과 같다.