The Java Program: B_counting/YiuBitCounting.java

  1 /*
  2 ACM ICPC Southeast Regional Contest 2010
  3 Problem: Bit Counting
  4 
  5 Author: Yiu Yu Ho
  6 */
  7 
  8 import java.io.*;
  9 import java.util.*;
 10 
 11 public class YiuBitCounting
 12 {
 13         public Scanner in = new Scanner(System.in);
 14         public PrintStream out = System.out;
 15     
 16     public long[][] cache;
 17     
 18         public void main() throws Exception
 19         {
 20         in = new Scanner( new File( "bitcounting.judge" ) );
 21         out = new PrintStream( new FileOutputStream( "bitcountingyiu.out" ) );
 22         cache = new long[65][65];
 23         for(int i = 0; i < cache.length; ++i) Arrays.fill(cache[i], -1);
 24     
 25         long low, high;
 26         int K;
 27         
 28         low = in.nextLong();
 29         while(low > 0)
 30         {
 31             high = in.nextLong();
 32             K = in.nextInt();
 33             
 34             out.println(solve(high, K) - solve(low-1, K));
 35             
 36             low = in.nextLong();
 37         }
 38         }//end public void main()
 39 
 40     public long solve(long n, int K)
 41     {
 42         if(n <= 0) return 0;
 43         if(K == 0) return 1;
 44         
 45         //n >= 2
 46         int[] v = bit(n);
 47         long[] C, P;
 48         
 49         C = new long[64];
 50         for(int x = 1; x < C.length; ++x) C[x] = go(v, v.length - 1, x);
 51         --C[1];
 52         
 53         for(int i = 1; i < K; ++i)
 54         {
 55             P = C;
 56             C = new long[64];
 57             for(int x = 2; x < P.length; ++x) C[f(x)] += P[x];
 58         }
 59         
 60         return C[1];
 61     }
 62     
 63     public int[] bit(long n)
 64     {
 65         int[] res = new int[64];
 66         for(int i = 0; i < res.length; ++i)
 67         {
 68             res[i] = (int)(n % 2);
 69             n /= 2;
 70         }
 71         return res;
 72     }
 73     
 74     public int f(int x)
 75     {
 76         int res = 0;
 77         while(x > 0)
 78         {
 79             res += (x % 2);
 80             x /= 2;
 81         }
 82         return res;
 83     }
 84     
 85     public long go(int[] v, int i, int B)
 86     {
 87         if(B < 0) return 0;
 88         
 89         if(i == 0)
 90         {
 91             if(B <= v[i]) return 1;
 92             return 0;
 93         }
 94         else
 95         {
 96             //i > 0, B >= 0
 97             if(v[i] == 0)
 98             {
 99                 return go(v, i-1, B);
100             }
101             else
102             {
103                 return C(i, B) + go(v, i-1, B-1);
104             }
105         }
106     }
107     
108     public long C(int n, int r)
109     {
110         if(n < r) return 0;
111         if(n == r) return 1;
112         if(r == 0) return 1;
113         
114         if(cache[n][r] >= 0) return cache[n][r];
115         return cache[n][r] = C(n-1, r) + C(n-1, r-1);
116     }
117     
118         public static void main(String[] args) throws Exception
119         {
120                 (new YiuBitCounting()).main();
121         }
122 }