题目描述

难度分:$1500$

输入$L$、$R(1 \leq L \leq R \leq 10^{18})$。

如果整数$x$的首位数字等于末位数字，那么称$x$是合法数字。

例如$101,477474,9$是合法数字，而$47,253,1020$不是合法数字。

输出$[L,R]$中有多少个合法数字。

输入样例$1$

2 47

输出样例$1$

12

输入样例$2$

47 1024

输出样例$2$

98

算法

数位DP

从高位往低位填数，先用函数$solve(s)$解决一个问题：给定$s$，$s$的长度为$n$，求$[1,s]$中有多少个合法数字。

状态定义

$dp[i][head][islimit][isvalid]$表示$[0,i)$位已经填好了，当前要填第$i$位，首尾数字填的是$head$（如果$head=0$表示还没填任何一个数字），$islimit$表示前面填的数位是否贴合上界$s$，$isvalid$表示$[0,i)$上面填的数位是否满足首尾等于末尾。因此，只要$i=n$且$isvaild=1$，就产生了一个合法数字。

状态转移

如果$head=0$，当前位仍然可以不填数，$dp[i][head][islimit][isvalid]=dp[i+1][head][0][0]$。

否则尝试填当前数位$d$，如果前面的数位贴合上界，当前数位最多只能填到$ub=s[i]$，否则$ub=9$。如果$head=0$，说明一直没有填过数，当前数位要从$lb=1$开始填，否则可以从$lb=0$开始填。枚举$d \in [lb,ub]$，状态转移方程为

$dp[i][head][islimit][isvalid]=dp[i+1][head][islimit \land d=s[i]][head=d]$，$head \gt 0$

$dp[i][head][islimit][isvalid]=dp[i+1][d][islimit \land d=s[i]][1]$，$head=0$

以上各种情况加起来就是$dp[i][head][islimit][isvalid]$的值，最终的答案就是$solve(R)-solve(L-1)$。

复杂度分析

时间复杂度

状态个数为$O(10 \times 2^2 \times log_{10}R)$，单次转移为$O(1)$，所以整体的时间复杂度为$O(10 \times 2^2 \times log_{10}R)$。

空间复杂度

空间消耗就是DP矩阵，因此额外空间复杂度为$O(10 \times 2^2 \times log_{10}R)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
LL L, R, dp[20][10][2][2];

LL solve(LL x) {
    string s = to_string(x);
    int n = s.size();
    function<LL(int, int, int, int)> dfs = [&](int i, int head, int islimit, int isvalid) {
        if(i == n) {
            return (LL)isvalid;
        }
        LL &v = dp[i][head][islimit][isvalid];
        if(v != -1) return v;
        LL cnt = head? 0: dfs(i + 1, head, 0, 0);
        int digit = s[i] - '0';
        int ub = islimit? digit: 9;
        for(int d = 1 - (head > 0? 1: 0); d <= ub; d++) {
            cnt += dfs(i + 1, head > 0? head: d, (islimit && d == digit)? 1: 0, (head == d || head == 0)? 1: 0);
        }
        return v = cnt;
    };
    memset(dp, -1, sizeof dp);
    return dfs(0, 0, 1, 0);
}

int main() {
    scanf("%lld%lld", &L, &R);
    printf("%lld\n", solve(R) - solve(L - 1));
    return 0;
}