数位DP

一、 度的数量

1、解析

• 题目翻译：满足条件的数x恰好等于k不互不相同的B的整数次幂之和，这等价于x的B进制中恰好有k个1，且只包含0或1
• 对于给定k和b求解区间[x, y]满足条件的数，相当于求前缀和s后，答案s[y] - s[x - 1]
• 此时这道题目转换成求解小于数字x = $a_{n-1}…a_0（B进制）$的所有满足条件的数
• 分类讨论，假设当前枚举到的数字是x, cnt表示当前已使用的1的个数：
  • x = 0: 保证枚举数字合法，则接下来的每一位必然都是0，只在最后一位是0的情况，总方案数需要+1
  • x = 1:
    • 放0: 接下来每一位可任意放置，方案数为c[i][k - cnt]
    • 放1: 接下来每一位不可随意放置，cnt++即可
  • x > 1:
    • 放0: 同x=1的情况
    • 放1: 同x=1的情况
    • 放其他的数字在本题不合法，直接break

2、代码

import sys
input = lambda: sys.stdin.readline().strip()

x, y = map(int, input().split())
k = int(input())
b = int(input())
n = 35
c = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(i + 1):
        if not j:
            c[i][j] = 1
        else:
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1]

def dp(x):
    if not x:
        return 0
    a, ans, cnt = [], 0, 0
    while x:
        a.append(x % b)
        x //= b

    for i in range(len(a) - 1, -1, -1):
        num = a[i]
        if num: # 存在左右分支
            ans += c[i][k - cnt] # 这一位放0
            if num > 1:  # 大于1的情况考虑放1或者大于1，大于1直接舍弃 
                if k - cnt - 1 >= 0:  # 可以放1
                    ans += c[i][k - cnt - 1]
                break
            else:  # 等于1的情况考虑放1，但由于需要保证数的合法性，通过下一位来考虑
                cnt += 1
                if cnt > k:    
                    break
        if not i and cnt == k:  # 最后一位放0也是一种方案 
            ans += 1

    return ans

print(dp(y) - dp(x - 1))

二、 数字游戏

1、解析

对于一个数字$x = a_{n - 1} a_{n - 2}…a_0 $求其不降数，假设当前枚举至第i位$ a_i $：
1)、如果选择$a_i$，则意味着无法保证数的大小，判断一些条件后接着枚举即可
2)、如果当前选择$[0, a_{i} - 1]$，则后续数位可以随意选择，只需满足不降条件即可，通过动态规划来求解，很容易知道当前位的选择只受到前一位的约束，定义f[n][i]表示长度为n的序列，第一位是i的不降数的方案数

关于前导0，由于数字就算存在前导0也仍然满足不降数，故不需要额外讨论

2、代码

import sys

lines = sys.stdin.readlines()
f = [[0] * 10 for _ in range(35)]
for st in range(10):
    f[1][st] = 1
for lens in range(2, 35):
    for st in range(10):
        for ed in range(st, 10): # 需要注意st才是高位
            f[lens][st] += f[lens - 1][ed]

def dp(x):
    if not x:  # 注意一个数字只有一位的时候，也算一个不降数
        return 1
    a, ans, maxs = [], 0, 0
    while x:
        a.append(x % 10)
        x //= 10

    for i in range(len(a) - 1, -1, -1):
        num = a[i]
        for j in range(maxs, num):
            ans += f[i + 1][j]

        if num < maxs:  # 提前去掉不满足不降条件的情况
            break
        maxs = num
        if not i:  # 当枚举到最后一位时，选择a[i]本身也是一种方案，因为在前面的情况没有将这一种加进来
            ans += 1

    return ans

for line in lines:
    x, y = map(int, line.strip().split())
    print(dp(y) - dp(x - 1))

三、 Windy数

1、解析

• 选择a[i], 此时向下继续枚举并判断相差是否大于等于2
• 选择[0, a[i] - 1]，此时方案数为f[i][x]，表示长度为n，最高位是x且相邻相差至少为2的所有方案数

2、代码

import sys

a, b = map(int, input().strip().split())
f = [[0] * 10 for _ in range(12)]
for i in range(10):
    f[1][i] = 1
for i in range(2, 11):
    for j in range(10):
        for k in range(10):
            if abs(k - j) >= 2:
                f[i][j] += f[i - 1][k]

def dp(x):
    if not x:
        return 0
    a, ans, last = [], 0, -2
    while x:
        a.append(x % 10)
        x //= 10

    for i in range(len(a) - 1, -1, -1):
        num = a[i]
        for j in range(int(i == len(a) - 1), num):
            if abs(last - j) >= 2:
                ans += f[i + 1][j]

        if abs(num - last) < 2:
            break
        last = num
        if not i:
            ans += 1
    for i in range(1, len(a)):
        for j in range(1, 10):
            ans += f[i][j]
    return ans


print(dp(b) - dp(a - 1))

四、 数字游戏II

1、解析

1)、首先考虑选择$[0, a_{n-1} - 1]$时，如何获取方案数。 要求所有位数字的和模n等于0，就需要知道一共多少位数，当前选择的数字是多少，以及前面数字之和是多少，分别记为n、x和sum
2)、动态转移方程：$f[n][x][sum] += f[n - 1][y][mod(sum - x, n)]$, 表示n位数最高位为x，前面的数字和为sum，可以从n - 1位最高位为y，数字和为sum - x的状态转移而来
3)、选择x时要求前面的数字和 + 后面的数据和模n等于0，(i.e. last + later) % n == 0, 也就是说后面可选数字的方案数为 f[i + 1][x][mod(-last, n)]

2、代码

import sys

lines = sys.stdin.readlines()
x, y, n = 0, 0, 0
f = [[[0] * 110 for _ in range(11)] for _ in range(11)]

def mod(x, p):
    return (x % p + p) % p

def init():
    global x, y, n, f
    # 注意：不要在init函数当中初始化f，否则会被认为是局部变量与全局变量，初始化失败
    # 如果要在init函数中进行初始化，则需要加上 gloabl f 
    f = [[[0] * 110 for _ in range(11)] for _ in range(11)]
    for i in range(10):
        f[1][i][i % n] = 1

    for i in range(2, 11):
        for j in range(10):
            for k in range(n):
                for p in range(10):
                    f[i][j][k] += f[i - 1][p][mod(k - j, n)]

def dp(x):
    if not x:
        return 1
    a, ans, last = [], 0, 0
    while x:
        a.append(x % 10)
        x //= 10    

    for i in range(len(a) - 1, -1, -1):
        num = a[i]
        for j in range(num):
            ans += f[i + 1][j][mod(-last, n)]

        last += num
        if not i and last % n == 0:
            ans += 1

    return ans


for line in lines:
    if line == '': continue
    x, y, n = map(int, line.strip().split())
    init()
    print(dp(y) - dp(x - 1))

五、 不要62

1、解析

等同的思路，每次判断是否存在 4 或者 62 跳过即可

2、代码

import sys

lines = sys.stdin.readlines()
f = [[0] * 11 for _ in range(15)]
for i in range(10):
    if i != 4:
        f[1][i] = 1
for i in range(2, 11):
    for j in range(10):
        for k in range(10):
            if j == 4: continue
            if k == 4: continue
            if j == 6 and k == 2: continue
            f[i][j] += f[i - 1][k]

def dp(x):
    if not x:
        return 1
    a, ans, last = [], 0, 0
    while x:
        a.append(x % 10)
        x //= 10

    for i in range(len(a) - 1, -1, -1):
        num = a[i]
        for j in range(num):
            if j == 4 or (last == 6 and j == 2):
                continue
            ans += f[i + 1][j]

        if num == 4 or (last == 6 and num == 2):
            break
        last = num
        if not i:
            ans += 1

    return ans


for line in lines:
    x, y = map(int, line.strip().split())
    if not x and not y:
        continue
    print(dp(y) - dp(x - 1))