这道题的目标是计算给定区间内有多少个“圆形数字”。根据题意，所谓的“圆形数字”是指该数字的二进制表示中零的位数大于或等于一的位数。我们需要通过高效的方式统计给定区间 [Start, Finish] 内的圆形数字的个数。

题解思路

1. 二进制表示：

   • 对于一个正整数 ( N )，我们可以通过其二进制表示来判断其是否为“圆形数字”。如果二进制表示中零的数量大于或等于一的数量，则该数字是“圆形数字”。
   • 比如数字 9，二进制是 1001，其中零的数量是 2，一的数量也是 2，因此 9 是一个圆形数字。
   • 另一个例子，数字 26，二进制是 11010，其中零的数量是 2，而一的数量是 3，所以 26 不是圆形数字。

2. 如何判断一个数是否是圆形数字：

   • 我们可以通过统计该数二进制表示中的零和一的数量来判断。如果零的数量大于或等于一的数量，则为圆形数字。

3. 关键问题：

   • 问题要求计算在一个非常大的区间 [Start, Finish] 内有多少个圆形数字，最大数字可以达到 20 亿，这意味着我们不能直接暴力遍历每个数，必须考虑更高效的方案。

4. 使用组合数和动态规划优化：

   • 由于计算每个数字的二进制表示的零和一的个数并判断是否是圆形数字的时间复杂度较高，所以我们采用动态规划结合组合数来加速计算。

代码分析

首先，代码通过组合数预计算来优化圆形数字的计数。C[i][j] 表示从 ( i ) 个元素中选 ( j ) 个的组合数。通过组合数，我们可以在计算过程中避免对每个可能的数字进行逐一枚举。

1. 初始化组合数表 C[i][j]：

   void init() {
       for(int i=0;i<=32;i++)
           for(int j=0;j<=i;j++)
               if(!j || i == j)
                   C[i][j] = 1;
               else
                   C[i][j] = C[i-1][j-1] + C[i-1][j];
   }
   

   • 这里计算了组合数 ( C[i][j] )，即从 ( i ) 个元素中选 ( j ) 个的组合数。我们使用了动态规划的方式来计算。

2. 计算从 1 到 ( l-1 ) 之间的圆形数字的个数：

   int total(int l) {
       int sum = 0;
       for (int i = 0; i < (l - 1) / 2; i++)
           sum += C[l - 1][i];
       if ((l - 1) % 2 != 0)
           sum += C[l - 1][(l - 1) / 2];
       return sum;
   }
   

   • 这个函数用于计算长度为 ( l ) 的二进制数字中，从 1 到 ( l-1 ) 的圆形数字的数量。通过组合数的性质，这部分计算是通过累加组合数来实现的。

3. 主函数 Sum：

   int Sum(int x, int flag) {
       int y = x;
       int a[35] = {0};
       int l = 0;
       for (int i = 0; x != 0; i++) {
           a[i] = x % 2;
           x /= 2;
           l++;
       }
       for (int i = 0; i < l / 2; i++) {
           int temp = a[i];
           a[i] = a[l - i - 1];
           a[l - i - 1] = temp;
       } // 得到 x 的二进制表示
   
       int w = 0; // w 用于统计总数
       for (int i = 1; i < l; i++)
           w += total(i); // 得到从 1 到 l 之间的圆形数字
   
       if (flag) { // 如果是第二个数据，要判断其是否为圆形数字
           int zeros = 0, ones = 0;
           for (int i = 0; i < l; i++)
               if (a[i] == 0)
                   zeros++;
               else
                   ones++;
           if (zeros >= ones) w++;
       }
   
       int zeros = 0;
       int ones = 1;
       for (int i = 1; i < l; i++) { // 计算等长的数中比给定值小的圆形数字
           zeros++;
           if (a[i] == 1) {
               int m = l - 2 * zeros;
               if (m >= 0) {
                   if (m % 2 != 0)
                       m = m / 2 + 1;
                   else
                       m = m / 2;
               } else
                   m = 0;
               for (int j = m; j <= l - zeros - ones; j++)
                   w += C[l - zeros - ones][j];
               ones++;
               zeros--;
           }
       }
       return w;
   }
   

   • 该函数的目的是计算从 1 到 ( x ) 的圆形数字的个数。
   • 它通过将 ( x ) 转换为二进制，然后根据该二进制形式计算圆形数字的数量。

4. 主函数：

   int main() {
       int a, b;
       init(); // 初始化组合数
       scanf("%d %d", &a, &b);
       int x = Sum(a, 0);
       int y = Sum(b, 1);
       printf("%d\n", y - x);
       return 0;
   }
   

   • 主函数首先初始化组合数表，然后读取输入的区间 [Start, Finish]。
   • Sum(a, 0) 计算从 1 到 ( a ) 的圆形数字个数，Sum(b, 1) 计算从 1 到 ( b ) 的圆形数字个数，最后输出 y - x 即为区间 [Start, Finish] 中圆形数字的个数。

总结

这段代码利用了组合数和二进制表示的性质，通过计算每个数字的二进制表示中的零和一的个数来判断该数字是否是圆形数字。同时，通过预计算组合数，避免了重复计算，使得整体算法可以在大范围内高效执行。