2013
11-12

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).

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

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

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.

1 1
1 0
2 1

1
1
0

//* @author:
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=0;
int k=0;
int m=0;

while(sc.hasNext()){
int a=0;
int b=0;
int c=0;
n=sc.nextInt();
k=sc.nextInt();
m=n-k;

while((n=n>>1)!=0) //将n的各二进制位右移一位，即相当于除以2
a+=n;

while((m=m>>1)!=0)
b+=m;

while((k=k>>1)!=0)
c+=k;

if(a-b>c)  //判断分子分母含2的个数的多少
System.out.printf("0\n");
else
System.out.printf("1\n");
}
}
}

1. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count