3219. Binomial Coefficients

The binomial coefficient C(n, k) has been extensively studied for its importance in combinatorics. Binomial coefficients can be recursively defined as follows:

C(n, 0) = C(n, n) = 1 for all n > 0;

C(n, k) = C(n − 1, k − 1) + C(n − 1, k) for all 0 < k < n.

Given n and k, you are to determine the parity of C(n, k).

Input. The input contains multiple test cases. Each test case consists of a pair of integers n and k (0 ≤ k ≤ n < 2³¹, n > 0) on a separate line.

End of file (EOF) indicates the end of input.

Output. For each test case, output one line containing either a “0” or a “1”, which is the remainder of C(n, k) divided by two.

Sample Input

1 1

1 0

2 1

Sample Output

1

1

0

РЕШЕНИЕ

комбинаторика - биномиальный коэффициент

Анализ алгоритма

C(n, k) нечетно тогда и только тогда, когда в двоичной записи числа k нет единиц в разрядах, в которых в двоичной записи числа n стоит ноль.

Пример

Рассмотрим выражение . Поскольку 11₁₀ = 1011₂, то будет нечетным только для таких k, у которых нет 1 во втором разряде (во втором разряде числа 11₁₀ стоит ноль).

будет нечетным при следующих значениях k : 0000₂ = 0, 0001₂ = 1, 0010₂ = 2, 0011₂ = 3, 1000₂ = 8, 1001₂ = 9, 1010₂ = 10, 1011₂ = 11.

Реализация алгоритма

#include <stdio.h>

int n, k;

int main(void)

{

while(scanf("%d %d",&n,&k) == 2)

printf("%d\n",k & (n-k) ? 0 : 1);

return 0;

}