배열 세기

문제 정보

문제

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개의 댓글이 있습니다.