244小U的问号替换问题

题解

给定一个由数字字符和 ? 组成的字符串，目标是将所有的 ? 替换为数字字符，使得替换后的字符串表示的十进制整数是正整数 p 的倍数。由于方案数可能非常大，需要对最终结果取模 (10^9 + 7)。

思路

使用动态规划的方法解决此问题。定义 f[i][j] 表示前 i 位替换后的数模 p 等于 j 的方案数。

动态规划状态

• 状态定义：f[i][j] 表示前 i 位替换后数模 p 等于 j 的方案数。
• 初始状态：f[0][0] = 1，表示前 0 位数模 p 为 0 的方案只有一种，即空串。
• 状态转移：
  • 对于每一位字符 c（从第 1 位到第 n 位）：
    • 如果 c 是 ?，则可以替换为 0 到 9 中的任意一个数字。
    • 如果 c 是具体数字，则只能替换为该数字。
  • 对于每一个可能的当前模值 j，更新新的模值 (j * 10 + k) % p，其中 k 是替换后的数字。
• 空间优化：由于每次只需要用到上一次的状态，可以使用滚动数组进行优化。

代码实现

# def solution(s: str, p: int) -> int:
#     n = len(s)
#     f = [[0] * p for _ in range(n + 1)]
#     f[0][0] = 1
#     for i, c in enumerate(s, 1):
#         for j in range(p):
#             if c == "?":
#                 for k in range(10):
#                     f[i][(j * 10 + k) % p] += f[i - 1][j]
#                     f[i][(j * 10 + k) % p] %= mod
#             else:
#                 f[i][(j * 10 + int(c)) % p] += f[i - 1][j]
#                 f[i][(j * 10 + int(c)) % p] %= mod
#     return f[n][0]

mod = int(1e9 + 7)

def solution(s: str, p: int) -> int:
    n = len(s)
    pre = [0] * p
    pre[0] = 1
    for i, c in enumerate(s, 1):
        cur = [0] * p
        for j in range(p):
            if c == "?":
                for k in range(10):
                    cur[(j * 10 + k) % p] = (cur[(j * 10 + k) % p] + pre[j]) % mod
            else:
                cur[(j * 10 + int(c)) % p] = (cur[(j * 10 + int(c)) % p] + pre[j]) % mod
        pre = cur.copy()
    return cur[0]

if __name__ == '__main__':
    print(solution("??", 1) == 100)
    print(solution("????1", 12) == 0)
    print(solution("1??2", 3) == 34)

复杂度分析

• 时间复杂度：$O(n \times p \times 10)$，其中 n 是字符串长度，p 是给定的正整数。
• 空间复杂度：$O(p)$