poj 3252 Round Numbers

Posted by

题目链接

http://poj.org/problem?id=3252

题意

定义一个数是Round Number,当它的二进制位(无符号位,不含前导\(0\))中\(0\)的个数大于\(1\)的个数。
给定\(a,b\),求\([a,b]\)中有多少个Round Number。

题解

考虑求出\([0,x)\)区间的Round Numbers。
设\(x\)二进制的长度为\(len\)。
对于长度不足\(len\)的数,无需考虑是否接触边界,贡献为\(\sum_{i=1}^{len-2}\sum_{j=\lfloor\frac{i}{2}\rfloor}^{i}C_{i}^{j}\),注意最高位一定为\(1\),故\(i\leq len-2\)。
对于长度为\(len\)的数,从高到底枚举每一位\(i\),\(cnt\)统计一定填\(0\)位的个数:

  1. \(x\)的当前位为\(0\),\(cnt++\);

  2. \(x\)的当前位为\(1\),先假设当前位填\(0\),贡献为\(\sum_{j=\lfloor\frac{len+1}{2}\rfloor-cnt-1}^{i-1}C_{i}^{j}\),之后假设当前位填\(1\),继续枚举。

答案差分一下,注意开闭区间的边界。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注