3644 - 인접 비트 카운팅

Time Limit: 3s Memory Limit: 128MB

Submissions: 24 Solved: 20
Description

n비트의 문자열 x1, x2, x3, ..., xn이 주어졌을 때 인접 비트 카운트 함수 AdjBC(x)는 다음과 같이 구해집니다.

x1 * x2 + x2 * x3 + x3 * x4 +...+ xn-1 * xn

즉, 1로 설정된 비트에 인접한 비트가 1인 횟수를 세는 것 입니다.

예를 들어, 9비트를 나타내는 문자열에 대한 값은..

AdjBC(011101101) = 3 
AdjBC(111101101) = 4 
AdjBC(010101010) = 0

과 같이 계산됩니다.

 

자, 여기까지는 사전 지식이었구요, 본 문제는 다음과 같습니다!

2개의 상수 n과 k가 주어졌을 때, n 비트의 문자열에서 AdjBC(x) = k 가 되는 경우의수를 세는 프로그램을 작성해 보십시오.

Input

* Line 1 : 단일 상수 N (문제의 수)

* Line 2 ~ N+1 : 3개의 상수 i n k

    - i : 문제 번호

    - n : 비트의 수 (최대 100)

    - k : AdjBC 함수의 결과 값

Output

* Line 1 ~ N : 2개의 상수 i o

    - i : 문제 번호

    - o : 계산된 경우의 수 (최대 231-1)

Sample Input
10
1 5 2
2 20 8
3 30 17
4 40 24
5 50 37
6 60 52
7 70 59
8 80 73
9 90 84
10 100 90
Sample Output
1 6
2 63426
3 1861225
4 168212501
5 44874764
6 160916
7 22937308
8 99167
9 15476
10 23076518
Hint

n=5 일때 k=2가 되기 위해서는 다음과 같은 6가지 경우가 존재합니다.

 

11100, 01110, 00111, 10111, 11101, 11011