数位DP解决二进制模式避免问题

1. 题目解析与解题思路

这道题目要求我们统计在给定区间[l,r]内，所有二进制表示中不包含"101"子串的整数的个数。乍一看这似乎是个简单的进制转换问题，但仔细分析后会发现几个关键点：

1. 暴力法的局限性：直接遍历区间内每个数并检查其二进制表示是否包含"101"的方法，在区间范围达到10^9时时间复杂度会变得不可接受(O(nlogn))，必然导致超时。

2. 数位DP的优势：数位动态规划(DP)是处理这类"数字各位满足特定条件"问题的利器。它通过记忆化搜索和状态压缩，将时间复杂度优化到O(logn)级别。

3. 问题转化：我们需要将问题转化为"在二进制表示中不出现特定模式(101)"的数字计数问题，这类似于字符串匹配中的模式避免问题。

2. 数位DP核心思想详解

数位DP的核心在于"按位处理+状态记忆"。对于本题，我们需要：

2.1 状态定义

定义递归函数dp(pos, limit, pre1, pre2)：

• pos：当前处理的二进制位位置
• limit：是否受到上界限制(即前面的位是否已经取到最大值)
• pre1：前一位的值(0或1)
• pre2：前两位的值(0或1)

2.2 状态转移

对于每一位，我们考虑两种情况：

1. 如果当前位取0：
   • 不会形成"101"，直接递归到下一位
2. 如果当前位取1：
   • 需要检查pre2和pre1是否为"10"，如果是则不能取1
   • 否则可以取1并递归

2.3 记忆化优化

使用一个四维数组memo[pos][limit][pre1][pre2]来存储已计算过的状态，避免重复计算。

3. 完整代码实现与解析

3.1 Java实现

java复制import java.util.*;

public class Main {
    static int[] num;
    static int[][][][] memo;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int r =