배열 세기

문제 정보

문제

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\)가 존재한다는 것과 같다.

3개의 댓글이 있습니다.