首页 > 专题系列 > Java解POJ > POJ 3219 Binomial Coefficients [解题报告] Java
2013
11-12

POJ 3219 Binomial Coefficients [解题报告] Java

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