题解

题面描述

给定区间 $[l,\;r]$ 和两个数字 $x$ 与 $k$，数字 $num$ 如果其各个位上的数字中 $x$ 恰好出现 $k$ 次，则称 $num$ 为“小美的幸运数字”。
题目要求计算在区间 $[l,\;r]$ 中有多少个幸运数字。

思路

由于区间的上界可以达到 $10^{12}$，无法对所有数字进行枚举，因此采用**数字动态规划（Digit DP）**进行统计。基本思路如下：

1. 区间转换
   先将问题转化为计算函数 $f(n)$，表示区间 $[0,\;n]$ 中满足条件的数字个数，然后答案为 $f(r) - f(l-1)$。

2. 状态设计
   在数字动态规划中设计状态：

   • $pos$：当前处理的位，从最高位到最低位，数字总长度记为 $L$。
   • $cnt$：已经在非前导零部分中出现了数字 $x$ 的次数。
   • $tight$：是否当前数字前缀与 $n$ 相等（若为 $1$，则当前位的数字上界为对应位上的数字，否则上界为 $9$）。
   • $started$：是否已经遇到非零数字（前导零不计入计数）。

3. 状态转移
   在每一位上枚举当前数字 $d$，更新状态：

   • 如果 $started$ 为 $0$ 且 $d=0$，则数字仍处于前导零状态，计数不改变。
   • 若数字开始（即 $started=1$）且 $d = x$，则令 $cnt$ 增加 $1$。
   • 当 $cnt > k$ 时该状态无效，不予转移。

4. 终止条件
   当 $pos = L$ 时，判断：

   • 若数字始终未开始（即数字为 $0$），则认为其表示为 “0”，此时若 $x=0$ 且 $k=1$，计数为 $1$；否则计数为 $0$。
   • 否则判断 $cnt$ 是否恰好等于 $k$，是则返回 $1$，否则返回 $0$。

5. 记忆化
   利用记忆化保存状态以防重复计算。

代码分析

• 状态转移：通过枚举当前位的数字 $d$（范围从 $0$ 到当前位上界），根据 $tight$ 与 $started$ 状态更新下一个状态，并增加计数（当且仅当数字已经开始且 $d=x$ 时）。
• 递归终止：当处理完所有位（$pos=L$）时，根据是否开始以及 $cnt$ 是否等于 $k$ 返回相应计数。
• 记忆化：使用多维数组（或缓存）存储状态 $dp[pos][cnt][tight][started]$，以降低时间复杂度。

C++ 代码

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

// 将数字转换为字符串表示
string toStr(ll n) {
    return to_string(n);
}

// 全局变量：
// dp 数组用于记忆化递归，vis 数组记录状态是否访问过
// dig 数组存储数字的每一位，L 表示数字长度
ll dp[20][20][2][2];
bool vis[20][20][2][2];
int dig[20];
int L;

// 数字动态规划递归函数
// cnt：已计数数字x出现的次数
// tight：是否受限于上界（0或1）
// started：是否已开始（0或1）
// x：目标数字x，k：要求出现次数k
ll solveDP(int pos, int cnt, int tight, int started, int x, int k) {
    if (pos == L) { // 处理完所有位
        if (!started) {
            // 数字全为前导零，此时数字为0
            // 如果x=0且k=1，则认为0中0出现一次
            return (x == 0 && k == 1) ? 1LL : 0LL;
        }
        return (cnt == k) ? 1LL : 0LL;
    }
    if (vis[pos][cnt][tight][started]) {
        return dp[pos][cnt][tight][started];
    }
    vis[pos][cnt][tight][started] = true;
    ll res = 0;
    int limit = (tight ? dig[pos] : 9);
    for (int d = 0; d <= limit; d++) {
        int ntight = (tight && (d == limit)) ? 1 : 0;      // 更新tight 状态
        int nstarted = (started || d != 0) ? 1 : 0;          // 更新 started状态
        int ncnt = cnt;
        // 如果数字已开始且当前位数字为x，则计数加1
        if (nstarted && d == x) ncnt++;
        if (ncnt > k) continue; // 超出要求次数则剪枝
        res += solveDP(pos + 1, ncnt, ntight, nstarted, x, k);
    }
    dp[pos][cnt][tight][started] = res;
    return res;
}

ll countLucky(ll n, int x, int k) {
    string s = toStr(n);
    L = s.size();
    for (int i = 0; i < L; i++) {
        dig[i] = s[i] - '0'; // 将字符转换为数字
    }
    memset(vis, 0, sizeof(vis)); // 重置记忆化数组
    return solveDP(0, 0, 1, 0, x, k);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll l, r;
        int x, k;
        cin >> l >> r >> x >> k;
        ll ans = countLucky(r, x, k) - countLucky(l - 1, x, k);
        cout << ans << "\n";
    }
    return 0;
}

Python 代码

# 使用数字动态规划计算幸运数字个数

from functools import lru_cache

def count_lucky(n, x, k):
    """
    计算区间 [0, n] 中满足条件的幸运数字个数
    n：上界数字
    x：目标数字
    k：要求出现次数
    """
    s = str(n)
    L = len(s)
    
    @lru_cache(maxsize=None)
    def dp(pos, cnt, tight, started):
        # cnt：已计数数字x出现的次数
        # tight：是否受限于上界（True 或 False）
        # started：是否已开始（True 或 False）
        if pos == L:
            if not started:
                # 数字全为前导零，即数字为0
                return 1 if (x == 0 and k == 1) else 0
            return 1 if cnt == k else 0
        res = 0
        limit = int(s[pos]) if tight else 9
        for d in range(limit + 1):
            ntight = tight and (d == limit)  # 更新 tight 状态
            nstarted = started or (d != 0)    # 更新 started 状态
            ncnt = cnt
            # 如果数字已开始且当前位为目标数字x则计数加1
            if nstarted and d == x:
                ncnt += 1
            if ncnt > k:  # 剪枝，超出要求次数
                continue
            res += dp(pos + 1, ncnt, ntight, nstarted)
        return res

    return dp(0, 0, True, False)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        l, r, x, k = map(int, input().split())
        # 答案为 count_lucky(r, x, k) - count_lucky(l - 1, x, k)
        print(count_lucky(r, x, k) - count_lucky(l - 1, x, k))

Java 代码

import java.util.Scanner;

public class Main {
    // 全局变量：
    // dp：用于记忆化的数组
    // vis：记录状态是否访问过
    // dig：存储数字的每一位，L 表示数字长度
    static long[][][][] dp;
    static boolean[][][][] vis;
    static int[] dig;
    static int L;
    
    // 数字动态规划递归函数
    // cnt：已计数数字x出现的次数
    // tight：是否受限于上界（0或1）
    // started：是否已开始（0或1）
    // x：目标数字x，k：要求出现次数k
    public static long solveDP(int pos, int cnt, int tight, int started, int x, int k) {
        if (pos == L) { // 处理完所有位
            if (started == 0) {
                // 数字全为前导零，即数字为0
                return (x == 0 && k == 1) ? 1L : 0L;
            }
            return (cnt == k) ? 1L : 0L;
        }
        if (vis[pos][cnt][tight][started]) {
            return dp[pos][cnt][tight][started];
        }
        vis[pos][cnt][tight][started] = true;
        long res = 0;
        int limit = (tight == 1) ? dig[pos] : 9;
        for (int d = 0; d <= limit; d++) {
            int ntight = (tight == 1 && d == limit) ? 1 : 0;    // 更新 tight状态
            int nstarted = (started == 1 || d != 0) ? 1 : 0;      // 更新 started状态
            int ncnt = cnt;
            // 若数字已开始且当前位为目标数字x则计数加1
            if (nstarted == 1 && d == x) {
                ncnt++;
            }
            if (ncnt > k) continue; // 剪枝，超出要求次数
            res += solveDP(pos + 1, ncnt, ntight, nstarted, x, k);
        }
        dp[pos][cnt][tight][started] = res;
        return res;
    }
    
    // 计算区间 [0, n] 中满足条件的幸运数字个数
    public static long countLucky(long n, int x, int k) {
        String s = Long.toString(n);
        L = s.length();
        dig = new int[L];
        for (int i = 0; i < L; i++) {
            dig[i] = s.charAt(i) - '0';
        }
        // 初始化 dp 和 vis 数组，维度为[L+1][k+2][2][2]
        dp = new long[L + 1][k + 2][2][2];
        vis = new boolean[L + 1][k + 2][2][2];
        return solveDP(0, 0, 1, 0, x, k);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long l = sc.nextLong();
            long r = sc.nextLong();
            int x = sc.nextInt();
            int k = sc.nextInt();
            // 答案为 countLucky(r, x, k) - countLucky(l - 1, x, k)
            long ans = countLucky(r, x, k) - countLucky(l - 1, x, k);
            System.out.println(ans);
        }
        sc.close();
    }
}

题目内容

小美认为一个数字$num$,如果其数位上的数字$x$恰好出现$k$次，那么认为$num$是她的幸运数字，请你帮助小美计算在$1$至$r$有多少个幸运数字。

输入描述

第一行一个整数$t(1≤t≤10^4)$,表示数据组数，对于每组数据格式为:

每行四个整数$l,r,x,k(1≤l≤r≤10^{12},0≤x≤9,1≤k≤12)$。

输出描述

对于每组数据输出一个整数，表示当前询问下的幸运数字个数。

样例1

输入

3
1 20 1 1
1 20 1 2
114514 5201314 5 2

输出

10
1 
550093