2683. 「BalticOI 2013」非回文数 题解

问题分析

我们需要统计区间 $[L, R]$ 内有多少个非回文数。非回文数的定义是：不包含长度大于 1 的回文子串。

例如：

• 16276 是合法的：没有长度≥2的回文子串
• 17276 不合法：包含 "727"（长度为3的回文）

关键点：

1. 回文子串长度可以是 2 或 3（因为更长的回文一定包含长度为2或3的回文）
2. 所以只需要检查相邻两位和间隔一位的情况

关键观察

1. 回文条件简化

一个数字不包含长度大于1的回文子串，等价于：

1. 没有相邻两位相同（避免长度为2的回文）
2. 没有间隔一位的两位相同（避免长度为3的回文，如aba形式）

形式化：对于数字的每一位 $d_i$，要求：

• $d_i \neq d_{i-1}$（避免 "aa" 型）
• $d_i \neq d_{i-2}$（避免 "aba" 型）

2. 问题转化

现在问题变为：统计 $[L, R]$ 内有多少个数字，其十进制表示中任意相邻两位不同，且任意间隔一位的两位也不同。

这是一个典型的数位DP问题。

数位DP设计

1. 状态定义

设 dp[pos][prev1][prev2][limit][lead] 表示：

• pos：当前处理到第几位（从高位到低位）
• prev1：前一位的数字（0-9，如果不存在则为10）
• prev2：前两位的数字（0-9，如果不存在则为10）
• limit：是否受到上界的限制
• lead：是否含有前导零

返回值：从当前位置开始，能构造出多少个合法数字。

2. 状态转移

对于当前位置，我们可以选择的数字 dig 范围是：

• 如果 limit = 1，则 dig ≤ upper[pos]
• 如果 limit = 0，则 dig ≤ 9

对于每个可能的 dig，需要检查：

1. 如果 lead = 1 且 dig = 0，则仍然是前导零状态
2. 否则：
   • 检查 dig ≠ prev1（避免长度为2的回文）
   • 如果 prev2 ≠ 10，检查 dig ≠ prev2（避免长度为3的回文）

3. 记忆化搜索

由于状态数有限：

• pos：最多 19 位（$10^{18}$ 有19位）
• prev1, prev2：各 11 种可能（0-9 + 不存在）
• limit, lead：各 2 种 总状态数：$19 \times 11 \times 11 \times 2 \times 2 ≈ 9196$，可以记忆化。

算法实现

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

ll dp[20][11][11][2][2];
string digit_str;
int digits[20];

// 记忆化搜索
// pos: 当前处理位置（0-based，从最高位开始）
// prev1: 前一位数字（10表示不存在）
// prev2: 前两位数字（10表示不存在）
// limit: 是否受到上界限制
// lead: 是否含有前导零
ll dfs(int pos, int prev1, int prev2, bool limit, bool lead) {
    // 如果已经处理完所有位
    if (pos == digit_str.length()) {
        return 1;  // 找到一种合法方案（空数字也算，但最终会减去）
    }
    
    // 记忆化
    if (dp[pos][prev1][prev2][limit][lead] != -1) {
        return dp[pos][prev1][prev2][limit][lead];
    }
    
    ll res = 0;
    int upper = limit ? digits[pos] : 9;
    
    for (int dig = 0; dig <= upper; dig++) {
        // 检查是否合法
        bool valid = true;
        
        if (!lead || dig != 0) {  // 如果不是前导零状态
            // 检查与前一位是否相同
            if (prev1 != 10 && dig == prev1) {
                valid = false;
            }
            // 检查与前两位是否相同（避免aba型回文）
            if (prev2 != 10 && dig == prev2) {
                valid = false;
            }
        }
        
        if (valid) {
            bool new_limit = limit && (dig == upper);
            bool new_lead = lead && (dig == 0);
            int new_prev1, new_prev2;
            
            if (new_lead) {
                // 仍然是前导零状态
                new_prev1 = 10;
                new_prev2 = 10;
            } else {
                // 不再是前导零
                new_prev1 = dig;
                new_prev2 = prev1;
            }
            
            res += dfs(pos + 1, new_prev1, new_prev2, new_limit, new_lead);
        }
    }
    
    return dp[pos][prev1][prev2][limit][lead] = res;
}

// 计算[0, x]内的非回文数个数
ll count_palindrome_free(ll x) {
    if (x < 0) return 0;
    if (x == 0) return 1;  // 0本身是合法的
    
    // 将x转换为字符串
    digit_str = to_string(x);
    int len = digit_str.length();
    
    // 提取每一位数字
    for (int i = 0; i < len; i++) {
        digits[i] = digit_str[i] - '0';
    }
    
    // 初始化DP数组
    memset(dp, -1, sizeof(dp));
    
    // 从最高位开始搜索
    // 初始：前一位和前两位都不存在，有限制，有前导零
    return dfs(0, 10, 10, true, true);
}

int main() {
    ll L, R;
    cin >> L >> R;
    
    // 计算[0, R]的个数减去[0, L-1]的个数
    ll ans = count_palindrome_free(R) - count_palindrome_free(L - 1);
    cout << ans << endl;
    
    return 0;
}

算法说明

1. 前导零处理

前导零需要特殊处理：

• 数字 "00123" 实际上是 "123"
• 在前导零状态下，不需要检查回文条件
• 只有当数字真正开始时（遇到第一个非零数字），才开始检查

2. 边界情况

• 数字 0：是合法的（不包含长度>1的回文）
• 个位数：总是合法的（没有长度>1的子串）
• 两位数：只要两位不同就合法

3. 复杂度分析

• 状态数：$pos \times 11 \times 11 \times 2 \times 2 ≈ 19 \times 484 = 9196$
• 每个状态最多尝试10个数字
• 总计算量：约 $10^5$ 量级，非常快

验证示例

样例1

输入：123 321

• 计算 [0, 321] 的个数减去 [0, 122] 的个数
• 输出：153 ✓

样例2

输入：123456789 987654321

• 计算 [0, 987654321] 的个数减去 [0, 123456788] 的个数
• 输出：167386971 ✓

正确性证明

1. 回文条件等价性

定理：一个数字串不包含长度≥2的回文子串，当且仅当它不包含长度为2或3的回文子串。

证明：

• 必要性：显然，如果包含长度≥2的回文，那么它要么包含长度为2的回文，要么包含长度为3的回文（因为更长的回文的中心部分会形成长度2或3的回文）
• 充分性：如果数字串既不包含 "aa" 型回文，也不包含 "aba" 型回文，那么它不可能包含更长的回文。因为任何长度≥4的回文，其中心部分必然包含长度为2或3的回文。

2. DP正确性

DP通过记忆化搜索枚举所有可能的数字，并在构造过程中检查：

1. 当前位与前一位是否相同（避免 "aa"）
2. 当前位与前两位是否相同（避免 "aba"） 这保证了最终得到的数字不包含任何长度≥2的回文子串。

总结

本题的关键点：

1. 理解非回文数的定义：不包含长度≥2的回文子串
2. 条件简化：只需要检查长度为2和3的回文
3. 数位DP应用：处理大范围区间统计
4. 前导零处理：前导零不影响回文检查

算法复杂度 $O(\text{状态数} \times 10)$，对于 $10^{18}$ 的范围完全可行。