The Java Program: B_counting/YiuBitCounting.java
1
2
3
4
5
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 }
39
40 public long solve(long n, int K)
41 {
42 if(n <= 0) return 0;
43 if(K == 0) return 1;
44
45
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
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 }