题目解析

该题目要求计算从 1 到 n 的每个数字进行乘法游戏后，结束在 0 到 9 每个数字的次数。乘法游戏的规则是：将一个数的各位数字相乘，用结果替换原数，重复直到结果为一位数。输入包含 t 天，每天给出一个 n_i，输出当天游戏结束在 0-9 的次数。

代码通过预处理和数位动态规划（Digit DP）的方式高效计算结果。以下是代码的详细解析：

1. 核心函数 g(n)

• 计算数字 n 进行乘法游戏的最终结果（一位数）。
• 如果 n 是一位数，直接返回 n。
• 否则，计算 n 的各位数字的乘积，然后递归调用 g。
• 使用记忆化数组 G 存储中间结果，避免重复计算。

2. 预处理 f 数组

• f[i] 是一个哈希表，表示长度为 i 的数字（包括前导零）的各位数字乘积为 p 的个数。
• 初始化 f[0][1] = 1，表示空数字的乘积为 1。
• 对于每个长度 i 从 0 到 17，遍历当前乘积 p 和计数 w，然后添加下一位数字 j（0-9），更新 f[i+1][j * p] 的计数。
• 这样，f[i] 包含了所有 i 位数字（允许前导零）的乘积分布。

3. 预处理 h 数组

• h[i] 是一个哈希表，用于优化剩余位数较多（≥10）时的计算。
• 对于长度 i 从 10 到 18，遍历 f[i] 中的每个乘积 p 和计数 w，再遍历 f[18-i] 中的每个乘积 q，计算 g(p * q) 并将计数 w 添加到 h[i][q][g(p * q)] 中。
• 这样，h[i][q] 是一个长度为 10 的数组，表示对于固定 q 和 i，游戏结果为 k 的次数。

4. 预处理 pre 数组

• pre[i] 是一个长度为 10 的数组，表示所有长度小于 i 的数字（即 1 到 i-1 位数）进行乘法游戏后，结束在每个数字的次数。
• 对于每个长度 i 从 1 到 18，pre[i] 初始化为 pre[i-1]，然后对于每个数字 j 从 1 到 9（第一位不能是零），遍历 f[i-1] 中的每个乘积 p 和计数 w，计算 g(p * j) 并更新 pre[i][g(p * j)]。
• 这样，pre[i] 累积了所有长度从 1 到 i 的数字的游戏结果分布。

5. 处理每个查询

• 对于每个 n，将其转换为字符串 u，获取位数 rem。
• 初始化答案 ans 为 pre[rem-1]，即所有位数小于 n 的数字的答案。
• 从高位到低位遍历数字 u 的每一位数字 x：
  • 设置 lead 标志表示是否在前导零部分（初始为 true）。
  • 对于当前位 x，遍历 j 从 0 到 x-1：
    • 如果 j=0 且 lead 为 true，则跳过（前导零无效）。
    • 如果剩余位数 rem ≥ 10，使用 h[rem][j * pr] 更新 ans，其中 pr 是当前已遍历各位数字的乘积。
    • 否则，遍历 f[rem] 中的每个乘积 p 和计数 w，计算 g(p * j * pr) 并更新 ans。
  • 更新 lead 为 false，pr 乘以 x。
• 将整个数字 n 的乘积 pr 对应的 g(pr) 加入 ans。
• 输出 ans 数组。

6. 时间复杂度分析

• 预处理 f、h 和 pre 数组的时间复杂度为 O(18 * 10 * K)，其中 K 是状态数，由于乘积分布稀疏，实际可接受。
• 每个查询的处理时间复杂度为 O(18 * 10 * L)，其中 L 是状态数，同样由于乘积分布稀疏，效率较高。
• 整体算法在 n ≤ 10^18 时高效。

样例验证

以样例输入 n=10 为例：

• 从 1 到 10 的数字的游戏结果：1→1, 2→2, 3→3, 4→4, 5→5, 6→6, 7→7, 8→8, 9→9, 10→0。
• 结束在 0-9 的次数各为 1，输出 1 1 1 1 1 1 1 1 1 1，与样例一致。

代码通过数位 DP 和预处理，高效地计算了大规模 n 下的结果分布。