培玉 · 一试
2016 年安徽预赛 · 第 8 题
F3填空题概率
等可能地随机产生一个正整数 ，则 在二进制下的各位数字之和不超过 的概率等于。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
用十一位二进制覆盖到 ，先按一的个数求完整区间计数，再扣掉零与超过题目上界的尾段。
思路
尾段共有固定的高位结构。
解答
至 可用所有十一位二进制串表示，补前导零不改变数字和。其中一的个数不超过八的串有
个。题目不含零，先减去一个。
又 的十一位写法是高六位全一、低五位全零。 至 则高六位全一，低五位从非零串中取值。要总共不超过八个一，低五位只能有一个或两个一，这样的尾段数有 。故题目范围内有利整数数目为 ，概率为
复核
本身只有六个一，应保留；被扣的尾段从 才开始。逐个统计 至 的二进制一的个数也得到 个合格数，即不合格者为 个。
方法总结
二进制数位计数可扩大到完整的二次幂区间，用组合数统计位数，再对不完整的高位尾段单独修正；零与上界端点要分别核查。
为什么评为 F3（会透露解法方向）
二进制计数可先补齐完整位串空间，再修正不完整高位尾段；零是否在样本、原上界是否保留须分开核。
已记下，谢谢！