题目描述

blablabla

样例

blablabla

算法

(计数dp)

Python 代码

# 初始化 帮助数组
#dp[i][j][u] 表示0到长度为i且最高位的数为j的数中u出现的个数
def init(n):
    dp = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(n + 1)]

    for i in range(10):
        dp[1][i][i] = 1

    for i in range(2, n + 1):
        for j in range(10):
            for u in range(10):
                # 当最高位j等于u时， 此时最高位的j有 10 ** (i - 1) 个， 即从0到i个99999
                if j == u:
                    dp[i][j][u] = 10 ** (i - 1)

                # 然后就是， 转移方程：当最高位为j时 dp[i][j][u] = dp[i - 1][k][u] k 属于[0, 9]
                for k in range(10):
                    dp[i][j][u] += dp[i - 1][k][u]

    return dp


# 计数dp的模板
def dp(n, u):
    if n == 0:
        return 1 if u == 0 else 0

    nums = []
    while n:
        nums.append(n % 10)
        n //= 10

    l = len(nums)
    dp = init(l)
    last = 0 #左边u的个数
    res = 0

    #从最高位开始循环
    for i in range(l - 1, -1, -1):
        #当前位的数
        cur = nums[i]

        # 分情况讨论计算符合的res, 先算左边的情况

        # 下面的情况讨论，每道题目都不同
        j = 0
        if i == l - 1:
            j = 1

        while j < cur:
            res += dp[i + 1][j][u]
            j += 1

        res += last * cur * 10 ** i

        if cur == u:
            last += 1

        # 最后计算剩下的右边情况，是否符合
        if i == 0:
            res += last

    for i in range(1, l):
        j = 0
        if i != 1:
            j = 1
        while j <= 9:
            res += dp[i][j][u]
            j += 1

    return res


if __name__ == '__main__':
    while True:
        n, m = list(map(int, input().split()))
        if n < m:
            n, m = m, n
        if n and m:
            for i in range(10):
                res = dp(n, i) - dp(m - 1, i)
                if i == 9:
                    print(res)
                else:
                    print(res, end=" ")
        else:
            break