高效统计大二进制数递归上下取整分拆最深层的1的数量

给定一个长度可达100万位的二进制字符串表示的数字X，按规则递归拆分后，计算仅出现在递归树最深层的1的数量（结果对10^9+7取模），解法如下：

核心规律总结 #

1. 判断是否为2的幂：如果二进制字符串是1后面跟全0（即X是2的幂），那么递归树最深层的1的数量为2^(n-1)，其中n是二进制字符串的长度。
   • 比如X=100（十进制4，n=3），结果为2^(3-1)=4。
2. 非2的幂情况：如果X不是2的幂，取二进制字符串去掉最高位后的子串，计算该子串对应的十进制数y，结果为(2*y) mod 1e9+7。
   • 比如X=111（十进制7，n=3），去掉最高位后的子串是11，对应y=3，结果为2*3=6，与题目示例一致。

具体实现步骤 #

步骤1：确定二进制字符串长度 #

设输入的二进制字符串为s，长度为n = len(s)。

步骤2：判断是否为2的幂 #

检查s[1:]（去掉第一个字符后的子串）是否全部由0组成：

• 如果是，说明X是2的幂，计算pow(2, n-1, 10**9+7)得到结果。
• 如果不是，执行步骤3。

步骤3：计算非2的幂情况的结果 #

遍历s[1:]的每个字符，逐步计算其对应的十进制数模1e9+7的值y：

mod = 10**9 + 7
y = 0
for c in s[1:]:
    y = (y * 2 + int(c)) % mod
result = (2 * y) % mod

示例验证 #

• 示例输入：111（十进制7）
  • n=3，s[1:]='11'不全为0，计算y=1*2+1=3，结果2*3=6，符合题目要求。
• 输入：100（十进制4）
  • s[1:]='00'全为0，结果2^(3-1)=4。
• 输入：101（十进制5）
  • s[1:]='01'，y=0*2+1=1，结果2*1=2。

内容的提问来源于stack exchange，提问作者md emon6767