“整数拼接记忆化更新”这个题目我最近正好在题库里刷到过。乍一看像是简单的两两拼数但真把数据规模拉大暴力枚举直接歇菜。这里的关键并不是拼接本身而是怎么把“拼接”这个操作拆成数学上可预处理的形态再用一块哈希表做增量更新把 O(n²) 压到接近 O(n)。这篇文章我把完整的推导、实现和踩坑过程都整理出来代码以 Python 为主思路同样可以用 C、Java 复刻。1. 先看题目本质拼接不是一个加法问题1.1 把拼接写成数学表达式先想清楚拼接到底是个什么运算。比如把12和345拼在一起得到的数是12345。它不等于12 345而是等于12 * 1000 345。因为345是三位数所以乘的是10^3。写成通式就是concat(a, b) a * 10^(len(b)) b其中len(b)是整数b的十进制位数。这个公式是整个题目的基石。这道题一般会这样描述给定一个数组nums对每一对不同的下标i和j把nums[i]和nums[j]拼接成一个整数统计拼接结果能被某个整数k整除的个数。注意“不同下标”意味着不能拿同一个元素自己拼自己。有了上面的公式判断能否整除就变成了判断(nums[i] * 10^(len(nums[j])) nums[j]) % k 0如果老老实实把每个拼接结果算出来再除一遍最容易想到。1.2 为什么不能硬拼整数暴力做法是这样的两层循环遍历所有i, j每次构造出真实的大整数然后取模。看起来代码很短但实际跑起来问题很多。第一是复杂度。数组长度n如果是10^5两两组合有10^10量级任何在线评测系统都会直接打回超时。第二是拼接出来的数可能巨大。假设数组里全是10^9级别的数两个拼一起就是10^18级别如果题目给的nums[i]本身是1e9拼接后超过 64 位整数范围也常见。第三把整数转成字符串再拼接再转回整数虽然写起来方便但每次都要做字符串内存分配常数巨大。真正需要的是不构造拼接结果只计算余数。这依赖于模运算的一个基本性质。1.3 模运算给了我们什么自由模运算满足如下两个规则(a b) % k ((a % k) (b % k)) % k (a * b) % k ((a % k) * (b % k)) % k所以concat(a, b) % k可以这样算concat(a, b) % k ((a % k) * (10^len(b) % k) (b % k)) % k这个转化很关键我们不需要知道a和b的真实值只需要知道它们各自的余数以及10^len(b)的余数。也就是说拼出来的数除以k余多少完全由三个小信息决定a对k的余数b的位数对应的10^len(b) % kb本身对k的余数再往深想一层a对k的余数只有k种可能而一个十进制整数的位数最多也只有有限的十几种。整个拼接判断的复杂度就大大降低了。提示这一段的结论是后续所有优化的入口。理解不透的话后面哈希表的设计会很别扭。2. 记忆化更新的设计思路2.1 从暴力到分桶谁是左边谁是右边很多人在读完上面的公式后会想那我按b的位数分类把每个数对k的余数存一下然后枚举左边的数去查表。这个方向是对的。具体来说对于一个固定的a要让concat(a, b)能被k整除我们需要(a % k) * pow10[len(b)] (b % k) ≡ 0 (mod k)也就是(b % k) ≡ -(a % k) * pow10[len(b)] (mod k)为了方便我们把b的所有信息按“位数”和“余数”组织对每个位数l维护一个计数表记录“余数为 r 的 b 出现了多少次”。查询时对每个可能的位数l算出右侧期望的余数target然后看对应表里target出现了几次。把所有l的结果加起来就是当前a作为左侧元素时能配成的对数。这就是分桶以右侧元素的位数为主键以元素余数为次键构建一组哈希表。2.2 状态定义长度、余数、出现次数具体落地的时候可以用 Python 的字典嵌套from collections import defaultdict table defaultdict(lambda: defaultdict(int)) # table[l][r] 表示位数为 l且对 k 取模为 r 的元素个数如果用 C可以用unordered_mapint, unordered_mapint, int如果k比较小更简单的方式是用二维数组table[len][r]比如k 1000时开[20][1000]就可以了。这里有个容易忽略的细节len指的是右侧元素b的十进制位数。比如b 5len 1pow10[1] 10b 123len 3pow10[3] 1000。位数相同的元素它们“放大”左侧元素时乘的系数是一样的这也是把位数作为第一维分桶的原因。预处理部分非常直接pow10_mod [1] * (MAX_LEN 1) for i in range(1, MAX_LEN 1): pow10_mod[i] (pow10_mod[i - 1] * 10) % k如果题目没有给最大位数上限可以先遍历一遍数组求出最长长度再开对应数组。这里不用pow(10, l, k)每轮都算因为幂次是递增的用递推更稳更快。2.3 增量更新的顺序问题到这里“记忆化”部分已经出现。我们要把扫描过程中已经遇到的元素信息“记忆”下来供后续元素查询。那么什么时候查、什么时候存顺序就很重要。用一句话概括每次取出一个新元素当作左侧元素a先在已记忆的集合里查询右边b的可配对数查完之后再把a自己按“右侧身份”加入记忆表。为什么要先查再存因为题目通常要求i ! j。如果先把当前元素存入表再查询那它可能自己匹配自己。比如数组是[1, 1]k 1如果先存再查同一个元素会被算成一对答案就错了。还有一个更深的原因每个元素最终被当作右侧元素的次数应该只反映“它左侧还有多少可用元素”。如果我们先查后存那么遍历到nums[i]时表里只包含下标小于i的元素。这样计数结果天然就是“从左往右”的单向统计不会重复。当然这里要看题目要求如果题目说(i, j)和(j, i)算两种不同组合那“从左往右”统计就少了一半需要在最后乘以 2如果只要求下标不同、不考虑顺序那这个结果直接就是答案。所以编码前必须先搞清楚题目要求不然这种小细节会埋雷。注意Python 里对负数的%运算会返回非负结果但 C 会得到负余数。后面写跨语言版本时要特别处理详见第 4 节。3. 核心实现与代码讲解3.1 预处理 10 的幂先说一个工程细节求整数位数。最简单的方法当然是转字符串len(str(num))但每次拼接都转字符串性能损耗很大。更推荐循环分解def get_len(x: int) - int: l 1 while x 10: x // 10 l 1 return l注意这里要求nums[i]是正整数。如果数据里包含0长度按 1 处理get_len要特殊判一下。预处理的完整代码MOD 10 ** 9 7 # 如果题目要求结果取模否则忽略 def solve(nums: list[int], k: int) - int: max_len 0 for x in nums: max_len max(max_len, get_len(x)) pow10 [1] * (max_len 1) for i in range(1, max_len 1): pow10[i] (pow10[i - 1] * 10) % k table defaultdict(lambda: defaultdict(int)) ans 0 for a in nums: l_a get_len(a) for l in range(1, max_len 1): # 期望右侧元素 b 满足 (a * 10^l b) % k 0 target (-a * pow10[l]) % k ans table[l][target] # 把当前元素 a 作为右侧信息存入 table[l_a][a % k] 1 return ans这段代码只有十几行却已经把第一、二章的数学推导全部串起来了。3.2 核心循环为什么要枚举位数第一次看这段代码的人可能会困惑为什么内层循环要把所有可能的位数都枚举一遍原因是左侧元素a只有一个位数但右侧元素b可以有各种不同的位数。比如a 12它后面可以接一位数3也可以接两位数45还可以接三位数678。每接一种位数拼接结果的位移量10^l就不一样对应的同余条件也就不一样。所以对固定的a我们得分别问右侧若是一位数目标余数是多少右侧若是两位数目标余数又是多少。每问一次就是一次查表。位数种类最多十几类所以内层循环代价很小。整体复杂度是O(n * L)L 为位数类别数十进制数的位数类别最多也就 10如果数不超过 32 位整数即使放宽到 64 位整数也只有 20。于是这个算法从平方量级降到了接近线性核心原因就在这。3.3 手算推演一个小用例写代码前强烈建议先手推一组小数据验证逻辑是否通顺。我用nums [1, 2, 3], k 3来推演。所有合法的拼接12 % 3 013 % 3 121 % 3 023 % 3 231 % 3 132 % 3 2答案是 2。用上面的代码跑一遍pow10[1] 10 % 3 1遍历第一个元素1l 1target (-1 * 1) % 3 2 table[1][2] 不存在ans 0然后存table[1][1] 1代表“一位数中余数为 1 的出现过一次”。遍历第二个元素2target (-2 * 1) % 3 1 table[1][1] 1ans 1这里配对的是2和已经出现过的1构成了21确实能被 3 整除。存table[1][2] 1。遍历第三个元素3target (-3 * 1) % 3 0 table[1][0] 0ans 1存table[1][0] 1。最终答案 1但我们手算是 2。问题在哪因为我们只统计了“当前元素作为左、之前元素作为右”的组合也就是下标顺序j i的组合。手算结果里的12是由1和2组成的在遍历到2时配对得到的是21没有算12。如果题目要求无序对那补齐另一半的顺序遍历即可。如果题目认为12和21是两个不同对象那答案确实是 1。这道题最常见的设定是i ! j(i, j)与(j, i)视为不同拼接结果。因此需要在第二遍中以数组倒序方式再统计一次或者直接对字典做对称统计。提示动手推演这组例子非常值。我每次给别人讲这道题都用这一组三步数据很快就能讲清楚顺序问题。4. 常见错误与排查实录4.1 先查后存还是先存后查这是这道题最容易错的地方。如果先存再查像nums [5, 5], k 5这类重复数字第一个5会被自身匹配直接多算一对。题目要求下标不同所以自匹配非法。解决办法就是严格先查后存。如果你在题目里看到答案总是偏大一般就是这里出了问题。4.2 负数取模在不同语言里的坑推导过程会出现-(a % k) * pow10[l] % k。在 Python 里-x % k的结果恒为非负数可以直接当作字典键。但 C 的%会保留负号比如-4 % 3 -1不是2。如果直接把负数放进哈希表后果是查表永远查不到。C 标准写法int target (k - (a % k) * pow10[l] % k) % k;这样强制转成正余数。Java 的%也保留符号同样需要处理。4.3 位数统计用错我见过有人直接用num / 10循环求位数结果遇到0或者100这类末尾带零的数就出错。0的长度应该算 1因为拼接123和0得到1230相当于123 * 10 0乘的确实是10而不是1。还有一批人图省事在循环里每次重新求len(str(x))虽然没逻辑错误但大数组下字符串转换开销不小拖慢常数。建议预处理一个长度数组一次性算好。4.4 暴力对拍验证写优化写法之前我强烈建议先写一个纯暴力的函数做对拍。比如def brute(nums, k): res 0 n len(nums) for i in range(n): for j in range(n): if i j: continue if int(str(nums[i]) str(nums[j])) % k 0: res 1 return res然后用随机数据跑几十组对比优化结果。比如nums [12, 345, 67, 8, 9]k 7把两边输出的答案对一多半心里就踏实了。这个小习惯帮我省了很多调试时间。4.5 答案超长要取模有些题会在最后要求对10^97取模。别等 ans 累加完再取因为中间可能溢出 64 位。在循环内部做ans (ans count) % MOD更安全Python 大整数虽然不怕溢出但习惯上仍建议保持统一写法。5. 可扩展方向5.1 如果 k 非常小当k 1000时哈希表的优势不明显可以直接用二维数组做计数表table [[0] * k for _ in range(max_len 1)]遍历时ans table[l][target] table[l_a][a % k] 1这样省去字典的哈希开销跑得更快代码也更简洁。k 很小的时候比如k 2甚至能手工总结规律进一步优化到只维护奇偶计数。5.2 如果 k 非常大k 10^9时同一个位数的余数类别很多但哈希表依然能扛。此时复杂度仍由位数类别数决定不会因为 k 变大而退化。这也是哈希表方案最大的优点——它不依赖 k 的范围。5.3 如果要求三元组拼接如果有人把题目升级为“三个数拼接”公式变成concat3(a, b, c) ((a * 10^len(b) b) * 10^len(c)) c可以沿用同样的思路先枚举(a, b)组合的余数和总长度再查询c。此时复杂度会多一层位数组合枚举一般来说需要再增加一个维度来记忆前两段的结果。这种题已经不多见但“记忆化更新”的思想完全一致把已经算过的组合状态记下来用增量查询代替重复计算。这个算法给我的最大启发是很多看似要枚举所有组合的问题只要能拆成“前段”和“后段”两个互相独立的部分并且每一段的信息可以压缩成少量状态就有机会用记忆化更新来降复杂度。整数拼接只是其中最典型的一个案例。碰到字符串拼接、二进制拼接、甚至多层嵌套的同余类题目都可以先想想这个框架。