题目描述

小明在学习二进制时，发现了一类不含 101的数，也就是：

将数字用二进制表示，不能出现 101 。

现在给定一个整数区间 [l,r] ，请问这个区间包含了多少个不含 101 的数？

输入描述

输入的唯一一行包含两个正整数 l， r（ 1 ≤ l ≤ r ≤ 10^9）。

输出描述

输出的唯一一行包含一个整数，表示在 [l,r] 区间内一共有几个不含 101 的数。

测试样例1

输入

1 10

输出

8

说明

区间 [1,10] 内， 5 的二进制表示为 101 ，10的二进制表示为 1010 ，因此区间 [ 1 , 10 ] 内有 10−2=8 个不含 101的数。

测试样例2

输入

10 20

输出

7

说明

区间 [10,20] 内，满足条件的数字有 [12,14,15,16,17,18,19] 因此答案为 7。

解题思路

要解决这个问题，我们需要计算在给定区间 ([l, r]) 内不含 101 子串的二进制数的数量。我们可以使用动态规划的方法来解决这个问题。

首先，我们需要理解如何计算一个给定长度的二进制数中不包含 101 子串的数量。我们可以定义两个状态：

• (a_n)：以 0 结尾的不含 101 的二进制数的数量。
• (b_n)：以 1 结尾的不含 101 的二进制数的数量。

对于长度为 (n+1) 的二进制数：

• 以 0 结尾的数可以通过在长度为 (n) 的任何有效二进制数后添加一个 0 来形成，因此 (a_{n+1} = a_n + b_n)。
• 以 1 结尾的数可以通过在长度为 (n) 且以 0 结尾的二进制数后添加一个 1 来形成，但不能在以 1 结尾的数后添加 1（除非它后面跟着的是 0），因此 (b_{n+1} = a_n)。

我们还需要一个初始状态：对于长度为 1 的二进制数，有 (a_1 = 1) 和 (b_1 = 1)。

现在，我们可以计算任意长度 (n) 的有效二进制数的数量，即 (a_n + b_n)。

接下来，我们需要将这个问题应用到给定的区间 ([l, r])。我们需要计算 (l) 和 (r) 的二进制表示，并找到包含 101 子串的最小和最大数。然后，我们可以使用动态规划计算这两个数之间的有效数的数量。

Python代码解析

def count_without_101(n):
    # 初始化动态规划数组
    a, b = 1, 1
    dp_a, dp_b = [1], [1]
    for i in range(n):
        dp_a.append(a + b)
        dp_b.append(a)
        a, b = dp_a[-1], dp_b[-1]

    return a + b


def count_without_101_in_range(l, r):
    count = 0
    for i in range(l, r + 1):
        bin_i = bin(i)[2:]
        if '101' not in bin_i:
            count += 1
    return count


# 测试样例1
l1, r1 = 1, 10
print(count_without_101_in_range(l1, r1))

# 测试样例2
l2, r2 = 10, 20
print(count_without_101_in_range(l2, r2))