题目内容

小明在学习二进制时，发现了一类不含 $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$ 。

题目描述

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

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

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

解题思路

要统计区间 [l, r] 内不含二进制子串 101 的数的个数，可以采用动态规划（DP）的方法，结合位运算来逐位判断数字的二进制表示是否包含 101。

具体步骤如下：

1. 二进制表示：将 r 转换为二进制字符串，方便从高位到低位进行处理。
2. 状态定义：
   • dp[pos][tight][prev2][prev1] 表示在当前处理到第 pos 位时，是否受限于上界（tight），以及前两位的状态（prev2 和 prev1）。
3. 状态转移：
   • 对于每一位，可以选择 0 或 1，但要确保不形成 101 的模式。
   • 如果当前位选择 1，需要检查前两位是否为 10，以避免形成 101。
4. 记忆化搜索：使用备忘录存储已经计算过的状态，避免重复计算。
5. 区间处理：计算 [0, r] 和 [0, l-1] 内不含 101 的数，然后相减得到 [l, r] 内的结果。

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// Memoization table
ll memo[32][2][3][3];
string num;

// DP函数
ll dp(int pos, int tight, int prev2, int prev1) {
    if (pos == num.size()) return 1;
    if (memo[pos][tight][prev2][prev1] != -1) return memo[pos][tight][prev2][prev1];
    
    int limit = tight ? (num[pos] - '0') : 1;
    ll res = 0;
    for(int digit = 0; digit <= limit; digit++) {
        int new_tight = tight && (digit == limit) ? 1 : 0;
        // 检查是否形成101
        if(prev2 == 1 && prev1 == 0 && digit == 1) continue;
        // 更新前两位
        int new_prev2 = prev1;
        int new_prev1 = digit;
        res += dp(pos+1, new_tight, new_prev2, new_prev1);
    }
    return memo[pos][tight][prev2][prev1] = res;
}

// 计算不含101的数的数量
ll countNumbers(string s) {
    num = s;
    memset(memo, -1, sizeof(memo));
    return dp(0, 1, 0, 0) -1; // 减1是因为0也被计入，需要排除
}

int main(){
    ll l, r;
    cin >> l >> r;
    // 转换为二进制字符串
    auto to_binary = [&](ll x) -> string {
        string s = "";
        if(x ==0) return "0";
        while(x >0){
            s += (x%2) + '0';
            x /=2;
        }
        reverse(s.begin(), s.end());
        return s;
    };
    string sr = to_binary(r);
    string sl = to_binary(l-1);
    ll ans = countNumbers(sr) - (l >1 ? countNumbers(sl) : 0);
    cout << ans;
}

python

import sys
sys.setrecursionlimit(10000)

def count_numbers(s):
    from functools import lru_cache
    n = len(s)
    
    @lru_cache(None)
    def dp(pos, tight, prev2, prev1):
        if pos == n:
            return 1
        limit = int(s[pos]) if tight else 1
        res = 0
        for digit in range(0, limit+1):
            new_tight = tight and (digit == limit)
            # 检查是否形成101
            if prev2 == 1 and prev1 == 0 and digit == 1:
                continue
            new_prev2 = prev1
            new_prev1 = digit
            res += dp(pos+1, new_tight, new_prev2, new_prev1)
        return res
    
    return dp(0, True, 0, 0) -1  # 减1是因为0也被计入，需要排除

def to_binary(x):
    return bin(x)[2:]

def main():
    l, r = map(int, sys.stdin.read().split())
    sr = to_binary(r)
    sl = to_binary(l-1) if l >1 else '0'
    ans = count_numbers(sr) - (count_numbers(sl) if l >1 else 0)
    print(ans)

if __name__ == "__main__":
    main()

java

import java.util.Scanner;

public class Main {
    private static String s;
    private static int n;
    private static Long[][][][] memo;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long l = scanner.nextLong();
        long r = scanner.nextLong();
        scanner.close();

        String sr = toBinary(r);
        String sl = l > 1 ? toBinary(l - 1) : "0";

        s = sr;
        n = s.length();
        memo = new Long[n + 1][2][2][2];
        long ansR = dp(0, 1, 0, 0);

        if (l > 1) {
            s = sl;
            n = s.length();
            memo = new Long[n + 1][2][2][2];
            long ansL = dp(0, 1, 0, 0);
            System.out.println(ansR - ansL);
        } else {
            System.out.println(ansR - 1); // 减1是因为0也被计入，需要排除
        }
    }

    // 将数字转换为二进制字符串
    private static String toBinary(long x) {
        return Long.toBinaryString(x);
    }

    // 动态规划函数
    private static long dp(int pos, int tight, int prev2, int prev1) {
        if (pos == n) {
            return 1;
        }
        if (memo[pos][tight][prev2][prev1] != null) {
            return memo[pos][tight][prev2][prev1];
        }
        int limit = tight == 1 ? Character.getNumericValue(s.charAt(pos)) : 1;
        long res = 0;
        for (int digit = 0; digit <= limit; digit++) {
            int newTight = tight == 1 && digit == limit ? 1 : 0;
            // 检查是否形成101
            if (prev2 == 1 && prev1 == 0 && digit == 1) {
                continue;
            }
            int newPrev2 = prev1;
            int newPrev1 = digit;
            res += dp(pos + 1, newTight, newPrev2, newPrev1);
        }
        memo[pos][tight][prev2][prev1] = res;
        return res;
    }
}