N比特流中X个连续真比特的概率计算问题（含特殊规则）

这是物理随机数随机性检测里很典型的连续比特计数问题，暴力遍历完全不现实（尤其是N到1e6时，2^1e6的规模根本没法处理），我们可以通过组合计数+数学化简的方式直接推导公式，高效算出总次数。

问题明确 #

我们要计算的是：所有长度为N的二进制串中，恰好出现X个连续1的总次数（注意：一个串里如果有多段不重叠的恰好X个连续1，每一段都要单独计入总次数）。
核心约束：统计的「恰好X个连续1」必须满足：

• 这段1的长度严格等于X
• 如果这段1不在串的开头，它的前一位必须是0；如果不在串的结尾，后一位必须是0（避免被更长的连续1包含）

公式推导 #

我们可以拆解每个可能的「恰好X个连续1」的位置，计算每个位置对应的合法串数量，再求和得到总次数：

分情况讨论 #

1. 当N = X时：
   只有全1的串符合条件，且仅存在1段恰好X个连续1，因此总次数为 1。

2. 当N > X时：
   我们把所有可能的起始位置s（从0到N-X）分成三类：

   • 起始位置在串开头（s=0）：需要第X位为0（防止连续1变长），后面N-X-1位可以任意取值，数量为 2^(N-X-1)。
   • 起始位置在串结尾（s=N-X）：需要第s-1位为0，前面s-1位可以任意取值，数量为 2^(N-X-1)。
   • 起始位置在中间（1 ≤ s ≤ N-X-1）：需要s-1位和s+X位都是0，剩余的N-X-2位可以任意取值，每个位置的数量为 2^(N-X-2)，共有N-X-1个这样的位置，总和为 (N-X-1)*2^(N-X-2)。

   把三类情况求和并化简：

   总次数 = 2^(N-X-1) + 2^(N-X-1) + (N-X-1)*2^(N-X-2)
          = 2*2^(N-X-1) + (N-X-1)*2^(N-X-2)
          = 2^(N-X) + (N-X-1)*2^(N-X-2)
          = 2^(N-X-2) * (4 + N - X - 1)
          = (N - X + 3) * 2^(N-X-2)
   

   注：当N-X-2为负数（也就是N=X+1）时，2^(负数)等价于1/2^|负数|，计算结果依然是整数，完全符合实际情况（比如N=X+1时，公式结果为(1+3)*2^(-1)=2，和手动统计的结果一致）。

验证示例 #

拿题目里的例子来说：N=16，X=5
代入公式计算：

总次数 = (16-5+3)*2^(16-5-2) = 14 * 2^9 = 14*512 = 7168

我们也可以用小范围手动计算验证逻辑，比如N=4,X=2时，公式给出结果5，和手动统计的所有符合条件的串的总次数完全一致。

高效实现代码 #

对于大N（比如1e6），我们可以用快速幂计算2^(N-X-2)，时间复杂度是O(log(N))，瞬间就能出结果。伪代码示例：

def calculate_exact_contiguous_ones(N, X):
    if X >= N:
        return 1 if X == N else 0
    exponent = N - X - 2
    if exponent >= 0:
        power_of_two = pow(2, exponent)
    else:
        # 负指数等价于分母，结果必为整数
        power_of_two = 1 // (pow(2, -exponent))
    return (N - X + 3) * power_of_two

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