codeforces-go 算法模板库实战：LeetCode 2081「k 镜像数字的和」回文数枚举与预处理全解析

• 科学计算

本文基于 codeforces-go 仓库中 leetcode/weekly/268/d/2081.md 的解题笔记展开，以 LeetCode 第 268 场周赛 T4「k 镜像数字的和」（Sum of K-Mirror Numbers）为例，完整讲解“从小到大枚举回文数 → 判定 k 进制镜像 → 前缀和预处理”的算法设计与多语言实现。读完本文，你将掌握回文数按长度有序生成的标准构造法、不转换字符串的 k 进制回文判定技巧，以及数据范围极小时“预处理打表 + O(1) 查询”的实战套路。

题目回顾与核心思路

题目要求：对给定的进制k（2 ≤ k ≤ 9）和数量n（1 ≤ n ≤ 30），求出前n个k 镜像数字的和。所谓 k 镜像数字，是指一个十进制下的回文数，其k 进制表示同样是一个回文数，且十进制数本身不能被 k 整除。

本题最关键的一个观察是数据范围极小：k只有 8 种取值，n最多 30，因此所有合法答案一共只有8 × 30 = 240个。既然答案总量如此有限，最稳妥的策略就是一次性把所有答案预处理出来，之后的每次查询直接查表，时间复杂度为 O(1)。

MAX_N = 30 ans = [[] for _ in range(10)] # ans[k] 存放第 k 进制下的前 30 个 k 镜像数字

对应仓库实现见 leetcode/weekly/268/d/d.go：const maxN = 30、var ans [10][]int，为 8 组k各预分配了容量maxN的切片（d.go）。

按长度有序生成回文数：左半边拼接法

要在“从小到大”的严格顺序下遍历所有回文数，经典做法是枚举左半边（前缀），把反转后的部分拼接到原数字末尾。设base = 10^0, 10^1, 10^2, …，对区间[base, 10·base)内的每一个数i：

• 奇数长度回文数：将i除末尾一位外的其余数位反转，拼到i后面。例如base = 10时，可生成[101, 999]中的全部奇数长度回文数。
• 偶数长度回文数：将i的全部数位反转，拼到i后面。例如base = 10时，可生成[1001, 9999]中的全部偶数长度回文数。

按“先奇数后偶数”的顺序遍历每一轮base，生成的回文数整体就是递增的：3 位回文数全部小于 4 位回文数，而 4 位回文数又全部小于 5 位回文数，以此类推。

以 Go 的纯整数实现为例（避免字符串转换的额外开销）：

for base := 1; ; base *= 10 { // 生成奇数长度回文数，例如 base = 10，生成的范围是 101 ~ 999 for i := base; i < base*10; i++ { x := i for t := i / 10; t > 0; t /= 10 { x = x*10 + t%10 } // x 即为奇数长度回文数，交给 doPalindrome 处理 } // 生成偶数长度回文数，例如 base = 10，生成的范围是 1001 ~ 9999 for i := base; i < base*10; i++ { x := i for t := i; t > 0; t /= 10 { x = x*10 + t%10 } // x 即为偶数长度回文数，交给 doPalindrome 处理 } }

完整代码见 d.go。这段“生成奇数/偶数长度回文数”的构造逻辑在仓库的算法模板 copypasta/common.go 中也有通用版本initPalindromeNumber，其注释明确标注了适用题目，包括LC2081 本題（common.go）、LC2967、LC906、LC3272 等，可作为回文数枚举题目的复用骨架。

枚举上界：左半边最多到 644545

预处理不能无限枚举，需要知道何时停止。原文档给出的精确结论是：枚举回文数的左半边时，要从 1 枚举到 644545，最后一个被用到的回文数为64454545446（11 位）。

值得注意：64454545446 > 2^31 - 1 ≈ 2.147×10^9，已经超出 32 位整数范围。因此：

• Go/Java/C++ 实现必须使用long long/int64（对应仓库中kMirror返回int64，见 d.go）；
• 判定终止时不能依赖 32 位溢出边界，而是像doPalindrome那样，当 8 组k各自的答案都收集满 30 个时立即结束（对应 d.go 中done标志的用法）。

k 进制镜像判定：不转字符串的「力扣 9」改造

对每个生成的回文数x，需要判断它是否为k = 2, 3, …, 9进制下的回文数。直接做法是转成 k 进制字符串再判断，而更高效的写法是改造经典题力扣 9「回文数」的原地反转算法——把每次“乘 10 加余数”改成“乘 k 加余数”：

// 力扣 9. 回文数 func isKPalindrome(x, k int) bool { if x%k == 0 { return false } rev := 0 for rev < x/k { rev = rev*k + x%k x /= k } return rev == x || rev == x/k }

几点值得展开：

• 提前剪枝x % k == 0：若x能被k整除，则其 k 进制表示以 0 结尾，而回文数的首位不可能为 0，所以它必然不是 k 镜像数字，直接返回false。这一行同时排除了所有十进制回文数中形如…0的数，能显著减少后续构造量。
• 只反转一半：循环条件rev < x/k意味着只反转数字的低位部分，当rev追上或超过剩余的高位部分时停止，避免把整个数反转完（那样会退化并需要处理溢出与全 0 边界）。
• 两种奇偶长度统一处理：终止时若rev == x（偶数长度）或rev == x/k（奇数长度）即判定为回文，与力扣 9 的标准解法一致，原文档也给出了该题解链接供对照。

仓库模板 copypasta/common.go 中的通用isPalindrome（十进制版本）注释同样引用了力扣 9 的题解，可对比参考其负数与末位为 0 的边界处理。

收集、终止与前缀和：把 30 个答案压成一次查询

收集与终止条件

doPalindrome的职责是：把当前回文数x分发给所有尚未收集满的k，并判断是否可以整体收工。其逻辑分三步：

1. 对k ∈ [2, 9]，若ans[k]还没收满 30 个且x是 k 镜像数字，则追加x（Go 中append自动扩容，但 init 已用make([]int, 0, maxN)预分配，见 d.go）；
2. 只要有任何一组k尚未收满，done就为false，继续枚举下一个回文数；
3. 当 8 组全部收满（done == true）时，对每组做前缀和并返回，外层init随即终止。

前缀和：把“前 n 个的和”降为 O(1)

题目要的是“前 n 个 k 镜像数字的和”，而不是第 n 个。若直接累加每个查询会变成 O(n)，因此预处理阶段就对每组答案原地求一次前缀和：

for k := 2; k < 10; k++ { // 计算前缀和 for i := 1; i < maxN; i++ { ans[k][i] += ans[k][i-1] } }

（见 d.go；Python 版用itertools.accumulate，Java/C++ 版分别用循环与partial_sum原地求前缀和。）

于是每次查询退化为一次数组下标访问：

func kMirror(k, n int) int64 { return int64(ans[k][n-1]) }

查询时的int64强转同样是为了兼容64454545446级别的中间和（第 30 个答案对应的前缀和更大，如测试用例中k = 2, n = 30的结果为2609044274，已超过 32 位有符号整数上限）。

复杂度分析

预处理部分的成本与题目查询无关，因此：

• 时间复杂度：O(1)（每次kMirror查询仅一次数组下标访问）；
• 空间复杂度：O(1)（固定大小的8 × 30张表）。

原文档的复杂度分析同样将预处理视为前置成本不计入，参见 2081.md「复杂度分析」一节。

仓库中的可运行验证：测试用例与执行方式

本仓库不仅给出了题解文档，还配套了可直接运行验证的 Go 实现与测试：

• 实现文件：leetcode/weekly/268/d/d.go；
• 测试文件：leetcode/weekly/268/d/d_test.go，内含 4 组官方示例：

其中最后一组k = 2, n = 30的输出2609044274印证了“前缀和结果远超 32 位整数范围、必须使用 64 位类型”的结论。

测试文件通过testutil.RunLeetCodeFuncWithExamples（定义于 leetcode/testutil/leetcode.go）驱动，这是仓库为 LeetCode 题目统一提供的样例驱动测试框架。运行方式：

cd leetcode/weekly/268/d go test

要点小结

1. 数据范围小到答案总量可穷举时，预处理打表 + O(1) 查询是最优套路：本题全部答案只有8 × 30 = 240个。
2. 回文数有序生成用“左半边反转拼接”：对每个base先奇数后偶数两轮构造，整体严格递增；该构造法在仓库模板 copypasta/common.go 中可直接复用。
3. k 进制回文判定 = 力扣 9 的进制替换：rev * k + x % k，配合x % k == 0剪枝，无需字符串转换。
4. 善用前缀和把“前 n 个的和”压成下标访问，并注意64454545446级别的中间值必须用 64 位整数承载。

延伸阅读

• 该题归类于回文数专项：原文档指向数学题单「§7.1 回文数」，仓库中 copypasta/common.go 的initPalindromeNumber、isPalindrome、getPalindrome三个模板函数（common.go）覆盖了回文数生成、判定与构造三类子问题；
• 若想系统刷题，可参考仓库 LeetCode 题解目录与分类题单（滑动窗口、二分、单调栈、位运算等十二大分类）。

• 科学计算