Time Limit: 3s
Memory Limit: 128MB
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 가 되는 경우의수를 세는 프로그램을 작성해 보십시오.
* Line 1 : 단일 상수 N (문제의 수)
* Line 2 ~ N+1 : 3개의 상수 i n k
- i : 문제 번호
- n : 비트의 수 (최대 100)
- k : AdjBC 함수의 결과 값
* Line 1 ~ N : 2개의 상수 i o
- i : 문제 번호
- o : 계산된 경우의 수 (최대 231-1)
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
1 6 2 63426 3 1861225 4 168212501 5 44874764 6 160916 7 22937308 8 99167 9 15476 10 23076518
n=5 일때 k=2가 되기 위해서는 다음과 같은 6가지 경우가 존재합니다.
11100, 01110, 00111, 10111, 11101, 11011