求助高中【数学帝】！ 组合数学题！ 文科生进来小心自卑……

Question

给出A,B

求A到B之间所有数字，转化成2进制下，0的数量大于等于1的数量，的数字个数。

比如
A=2 B=12 答案是6
A=1 B=128 答案是50

当A=1000 B=2009 答案是多少？

PS:高中数学题 不知道，

其实，最夸张的的问：A=1，B=2^32-1 差不多就是 A=1 B=2000000000~

给个思路，给个想法。纠结超过12个小时了。 据说是动态规划求端点，可是我的想法就是做不对、

求思路

Answer 1

只选取大于零的数来计算。
由于任意大于零的数转化为二进制首位必为1，
则满足条件的最小的二进制数为10（也就是2^1）。
将所有二进制数由小到大排列，
取分点10，100，1000，10000，...，
即十进制下的2^N （N为整数且N>=1）为分点
分点间的数为一类，其实也就是按照二进制数的位数进行分类

对于N+1位的二进制数（首位为1，余下的N位可选0或1两种选择）
则要想满足条件，即0的数量大于等于1的数量
当N+1为奇数时，在除首位的N个数位上至少要选N/2+1个零
当N+1为偶数时，在除首位的N个数位上至少要选(N+1)/2个零
用C(n,m)表示从m个元素里选n个元素的组合数，
可计算满足题目的数的个数
当N+1为奇数时，满足条件的个数为
C(N,N)+C(N-1,N)+C(N-2,N)+...+C(N/2+1,N)
当N+1为偶数时，满足条件的个数为
C(N,N)+C(N-1,N)+C(N-2,N)+...+C((N+1)/2,N)

所以任给两个数字，可先转化为二进制数，然后分类计算
例题中A=1=2^0 B=128=2^7（及小于8位的数）
可分类算两位中满足的有C(1,1)=1
三位中满足的有C(2,2)=1
四位中满足的有C(3,3)+C(2,3)=4
五位中满足的有C(4,4)+C(3,4)=5
六位中满足的有C(5,5)+C(4,5)+C(3,5)=16
七位中满足的有C(6,6)+C(5,6)+C(4,6)=21
共计50个

例题中A=1000 即二进制 1111101000
B=2009 即二进制11110011001

可看出只有10位或11位两类

对于10位的因为从 1111101000至1111111111中，
凡是大于1111101000的前5位必然固定取1了 不可能取到5个0
所以期间没有符合条件的

对于11位的
从10000000000至11111111111即（2^10至2^11-1中）
满足的总共有C(10,10)+C(9,10)+C(8,10)
+C(7,10)+C(6,10)=386

而凡是大于11111100000的11位数已经不可能有符合题目的
只需再计算11110011001至11111100000之间的从总数中减掉即可
11110011001至11111100000之间的
其实相当于10011001至11100000之间的（前三位只能取1）

分三段取10011001至10011111
10100000至10111111
11000000至11111111 观察首位固定的1
上述三段可简化为 1001至 1111 （四位 共4-1=3个）
100000至 111111 （六位 共16个）
1000000至 1111111 （七位 共21个）

所以答案为386-3-16-21=346个，完毕。

Answer 2

我觉得用排列组合的方法再找一下规律应该可以出来吧，虽然可能没你的正确方法简单。。。
1000=512+256+128+64+32+8=2^9+2^8+2^7+2^6+2^5+2^3=1111101000,同理，2009=11111011001。考虑一下二进制数0和1变化的规律，在把它当成从哪些位置选几个出来作为1，剩下的为0（排列组合），稍微想了一下，感觉应该能出答案了。

Answer 3

额才11。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。太深奥了

Answer 4

zxvsdzvgsadg