请统计某个给定范围[L,R]的所有整数中，数字x出现的次数。 比如给定范围[2,22]，x=2：数字2在该范围内一共出现了6次。

算法1：暴力枚举

对于[L,R]中的每一个数，我们将它转化为字符串，然后遍历字符串中的每一位，如果当前位为x，则计数器加1。最终计数器的值即为数字x在[L,R]中出现的次数。

时间复杂度：O((R-L)logR)

算法2：数位分解

我们可以将[L,R]按照数位分解的方式分成若干个区间，每个区间内的数的某一位都是相同的。比如说，对于区间[1000,2999]，它们的千位上都是1。这样，我们就可以分别计算每个区间内数字x出现的次数，最终把所有区间的计数器相加即可。

具体做法如下：

1. 首先，我们需要求出[L,R]的位数，设为n。比如说，如果L=123，R=7890，那么n=4。

2. 从高到低枚举每一位，设当前枚举的是第i位，范围是[1,n]。我们记[L,R]在第i位之前（高于i位）的数分别为left，右边（低于等于i位）的数分别为right。

3. 对于当前位i，我们分别计算数字x在left、right中出现的次数。设当前位的权值为base（比如说，如果i=2，那么base=10），则在left中，数字x在第i位出现的次数为：

- 如果x=0，那么left中第i位出现0的次数为：(left/base-1+1)×base=left，其中(left/base-1+1)是left中有多少个base的倍数，乘以base就是0出现的次数。
- 如果x>0，那么left中第i位出现x的次数为：(left/base)×base，其中(left/base)是left中有多少个base的倍数，乘以base就是x出现的次数。

在right中，数字x在第i位出现的次数为：

- 如果x=0，那么right中第i位出现0的次数为：(right%base+1)。
- 如果x>0，那么right中第i位出现x的次数为：min(right%base+1, base)。

4. 将所有区间内数字x出现的次数相加，即为答案。

时间复杂度：O(logR)

算法3：数位 DP

我们用f[i][j]表示当前处理到第i位，上一位数字为j时，数字x在[L,R]中出现的次数。转移时可以枚举当前位填哪个数字，然后根据当前位填的数字以及上一位填的数字，计算出当前状态转移到的状态。具体地：

1. 初始化f[0][0]=1，表示处理到第0位时，数字x在[L,R]中出现的次数为0。

2. 从第1位开始枚举每一位，设当前枚举的是第i位，范围是[1,n]。对于每个状态f[i][j]，我们考虑它转移到哪些状态：

- 如果当前位可以填数字x，则状态f[i][j]可以转移到f[i+1][j]，此时数字x在第i位上出现了1次。
- 如果当前位不可以填数字x，则状态f[i][j]可以转移到f[i+1][k]，其中k是当前位可以填的数字，此时数字x在[L,R]中不出现。

3. 最终答案为f[n][0]。

时间复杂度：O(logR)

参考代码：

算法2：

def count_digit(n, x):
    res = 0
    base = 1
    while n > 0:
        left = n // 10
        cur = n % 10
        right = 0
        if x == 0:
            if left > 0:
                left -= 1
                right = base
        res += left * base
        if cur > x:
            res += base
        elif cur == x:
            res += right + 1
        base *= 10
        n //= 10
    return res

L, R, x = map(int, input().split())
ans = count_digit(R, x) - count_digit(L-1, x)
print(ans)

算法3：

L, R, x = map(int, input().split())
n = len(str(R))
f = [[0] * 10 for _ in range(n+1)]
f[0][0] = 1
for i in range(1, n+1):
    for j in range(10):
        for k in range(10):
            if j == x and k != x:
                f[i][j] += f[i-1][k]
            elif j != x:
                f[i][j] += f[i-1][k]
ans = sum(f[n])
if x == 0 and L == 1:
    ans -= sum(f[n-1][:1])
for i in range(1, n):
    ans -= f[i][0]
print(ans)