看到题目名里的“回文数”，可能有人觉得这题简单：不就是判断一个数字正着读反着读一样吗？但等你真打开洛谷P1015或者信息学奥赛一本通1309，看到题目给的进制可以是2到16，数字最长能到100位，还要在30步内反复做“原数加倒序数”的操作，才会意识到这道NOIP1999普及组老题，真正想考的是三件事：进制转换、高精度加法、回文串判断。
我第一次做这道题时也犯过“觉得简单”的毛病，用long long存数字，样例倒是过了，一提交就WA。后来老老实实改成字符串模拟，才把题目吃透。这篇文章就把我的完整思路、参考代码、踩坑经历都写出来，适合刚接触高精度的入门选手，也适合准备NOIP普及组复赛、想系统过一遍字符串模拟加法的人。
1. 先别急着写代码：题目里的三个关键词
1.1 这道题和“普通回文数”有什么不同
普通回文数题一般只让你判断一个十进制整数是不是回文数，写个反转比一比就结束。P1015不是这种玩法，它给了你一个N进制数M，N可以是2到10，也可能是16。这意味着输入里可能出现大写字母A到F，而且每一步加法都必须遵守N进制的进位规则，不能按十进制算完再转回去。
举个例子，N=16时，M=5，它的倒序数还是5，相加得到A（十进制10）吗？不是，5+5=10，在十六进制里写作A，这没问题。但如果M=A，倒序还是A，A+A=20（十六进制），也就是十进制32。如果按十进制算，10+10=20，然后把20转成十六进制也是14？等等，这里很容易乱。正因为容易乱，所以正确的做法是全程在N进制字符串上操作，不要中途转到十进制。
还有个麻烦点：M的长度最长可以到100位。100位的十进制数本身已经远超long long范围，更不用说N=16时每一位还是字符。这也是为什么这道题必须走高精度路线。
1.2 30步是怎么来的
题目要求如果在30步以内（含30步）得到一个回文数，就输出STEP=步数，否则输出Impossible!。
这个30步不是随便写的。每做一次“原数加倒序数”，结果最多比原来多一位，因为高精度加法里最高位进位最多是1。假设初始M有100位，30步之后最多130位。用字符串模拟，每次加法复杂度O(L)，判断回文也是O(L)，总复杂度O(30L)，非常稳定。这个“数据规模提示算法”的思路，在竞赛题里很常见，看到30步、100位这类数字，就该想到不是让你暴力用整数类型硬扛。
顺便说一个背景知识：十进制下有个著名的“196问题”，指的是某些数反复加上它的倒序数，目前也不确定最终能不能得到回文数。竞赛题把步数限制在30，相当于给了确定的终止条件，所以输出Impossible!并不是bug，而是题目设计的一部分。
1.3 先自己推一遍样例
题面给的样例通常是N=10，M=87，输出STEP=4。我们手动推一遍：
- 87 + 78 = 165，不是回文
- 165 + 561 = 726，不是回文
- 726 + 627 = 1353，不是回文
- 1353 + 3531 = 4884，是回文
所以答案是4。
这个手推过程能帮你避开一个常见误解：题目说的“把这个数加上它的倒序数”，不是把字符串拼在一起。比如165 + 561，个位5+1=6，十位6+6=12，十位要进位，所以结果是726，而不是“165561”。真正的竖式加法，必须处理进位。
2. 高精度加法为什么必须写成字符串模拟
2.1 从long long溢出说起
初学者最容易犯的错，就是把输入的数字转成long long，然后循环相加和判断。如果M只有两三位，这个做法能过样例，但正式数据一上去就WA。原因很简单：100位的数字，long long根本存不下，而且每次相加位数还在变化，30步之后最长130位，用C++的整数类型毫无机会。
所以正解是字符串模拟手算竖式。这也是信息学竞赛“高精度”知识点的标准套路：把大数按位拆开，逐位相加，逢N进一。用string存的好处是长度不固定，动态变化时不需要手动扩容。如果你刚学高精度，用vector存数字也可以，但string在本题里写起来更顺手。
2.2 竖式加法的核心逻辑
假设有两个字符串a和b，表示两个N进制数。它们的长度一定相同，因为b是a的倒序。从右往左逐位处理：
- 取出a当前位和b当前位，转成整数；
- 加上上一位的进位carry；
- 当前位的结果是sum % N；
- 新的进位是sum / N。
因为N进制下两个一位数相加，再加上一个进位，sum最大是(N-1)+(N-1)+1=2N-1，所以carry只会是0或1。这个结论能帮你理解，但代码里写成通用的sum / base最稳妥，以后遇到任意进制也不用改。
举例，十进制87+78：
- 个位：7+8=15，写5，进1；
- 十位：8+7+1=16，写6，进1；
- 最高位进位1写到最前面，得到165。
如果最高位有进位，千万别丢掉。很多人写循环时条件写成while (i >= 0 || j >= 0)，两个字符串都扫描完就退出，导致最后的carry没处理，直接WA。
2.3 为什么逆序数就是原串反转
题目说“把这个数加上它的倒序数”，倒序数就是原字符串的反转。比如M="1234"，倒序数就是"4321"。字符串反转在C++里可以直接用reverse(s.begin(), s.end())，Python里用s[::-1]。
但这里有个隐蔽问题：反转操作会改变原字符串。C++的reverse是原地反转，Python的切片反转不会改变原串。如果你在判断回文时直接对原串reverse，下一步做加法时，原串已经被改成倒序了，算出来的结果就会出错。正确做法是先把原串复制一份，再对副本反转。这个“拷贝后再反转”的习惯，能帮你避开大量字符串题目的坑。
3. 完整代码与逐段讲解
3.1 C++参考实现
我直接给出一份能过的C++代码，代码风格偏竞赛，注释写在关键位置：
#include <bits/stdc++.h> using namespace std; int N; string M; int val(char c) { if (c >= '0' && c <= '9') return c - '0'; return c - 'A' + 10; } char toChar(int x) { if (x < 10) return char('0' + x); return char('A' + x - 10); } string add(string a, string b) { string res; int carry = 0; int i = a.size() - 1, j = b.size() - 1; while (i >= 0 || j >= 0 || carry) { int sum = carry; if (i >= 0) sum += val(a[i--]); if (j >= 0) sum += val(b[j--]); res.push_back(toChar(sum % N)); carry = sum / N; } reverse(res.begin(), res.end()); return res; } bool isPal(const string& s) { string r = s; reverse(r.begin(), r.end()); return s == r; } int main() { cin >> N >> M; for (int step = 0; step <= 30; step++) { if (isPal(M)) { cout << "STEP=" << step << endl; return 0; } if (step == 30) break; string rev = M; reverse(rev.begin(), rev.end()); M = add(M, rev); } cout << "Impossible!" << endl; return 0; }几个细节值得说明：
val和toChar负责字符和数字之间的转换，覆盖16进制的A-F。如果输入里有小写字母，最好在输入后统一转大写，for (char &c : M) c = toupper(c);。add函数中while循环条件带carry，所以最高位的进位不会丢。- 主循环用
step从0到30，先判断再决定是否继续加。这样初始就是回文数时会输出STEP=0，第30次加法后才变成回文的也能输出STEP=30，不会漏判。
3.2 Python参考实现
Python写起来更短，适合快速验证思路：
def to_val(ch): if '0' <= ch <= '9': return ord(ch) - ord('0') return ord(ch.upper()) - ord('A') + 10 def to_char(x): return str(x) if x < 10 else chr(ord('A') + x - 10) def add(a, b, base): res = [] carry = 0 i, j = len(a) - 1, len(b) - 1 while i >= 0 or j >= 0 or carry: s = carry if i >= 0: s += to_val(a[i]) i -= 1 if j >= 0: s += to_val(b[j]) j -= 1 res.append(to_char(s % base)) carry = s // base return ''.join(reversed(res)) n = int(input()) m = input().strip().upper() for step in range(31): if m == m[::-1]: print(f"STEP={step}") break if step == 30: print("Impossible!") break m = add(m, m[::-1], n)Python的m[::-1]不会改变原字符串，所以C++里“拷贝后再反转”的问题在Python里不存在。但要注意''.join(reversed(res))的顺序，res是从低位开始存储的，必须反转回来才是正确结果。
3.3 时间复杂度与数据范围
单次加法扫描整个字符串，回文判断也扫描一次，所以每轮是O(L)，L是当前数字长度。因为每加一次最多增加1位，所以从初始长度L0开始，30轮后长度不超过L0+30。总复杂度O(30 * (L0 + 30))。就算初始M有100位，字符操作也就几千次，在评测系统上几乎是0ms。这道题真正的难点从来不是性能，而是逻辑细节。
4. 变式题与常见误区：进制、回文、高精度三者的组合
4.1 误区一：先把M转成十进制再算
有些同学会问：能不能先把M转成十进制，在十进制里做高精度加法，再转回N进制？理论上是可行的，但不推荐。原因在于，M本身是N进制数，按N进制加法规则直接在字符串上模拟，不需要经过十进制。如果先转十进制，100位的N进制数转成十进制后依旧是个大数，还得再写一套十进制高精度，做完再转回去，代码量直接翻倍。
正确的思路是：把“N进制高精度加法”封装成一个函数，任何进制都通用。只要处理好toChar和val，代码可以兼容2到16进制，这也是这道题最值得收藏的模板价值。
4.2 误区二：判断回文和生成倒序数混在一起
判断回文的本质是“原串 == 反转串”。生成倒序数的本质是“取反转串”。这两个操作看起来很像，但使用场景完全不同。
每次循环里正确的顺序是：
- 先判断当前串是否是回文；
- 如果不是，生成反转串，做加法；
- 把结果作为新的当前串。
如果在判断回文时把原串反转了，下一步生成反转串得到的其实是一开始的顺序，结果必然会错。C++的isPal函数内部要拷贝一份再reverse，add函数里也要先拷贝原串再反转。
4.3 误区三：输入字母大小写不一致
NOIP1999原题给的是大写A-F，但有些数据或变式题可能给小写。稳妥起见，读入之后统一转大写：
- C++：
for (char &c : M) c = toupper(c); - Python：
m = input().strip().upper()
否则val函数遇到小写字母会返回错误的结果。写这种进制字符串题目，先搞定字符和数字互转，再写主逻辑，能省下大量调试时间。
4.4 从这道题延伸出去的变式
如果题目改成“输出每一轮的结果”，你只需在循环里把M打印出来。如果改成“步数上限是1000”，调整range和判断逻辑就行，算法完全不用变。如果以后遇到“高精度回文数”“N进制加法”类题目，核心模板就是这套：val、toChar、add、isPal四个函数组合使用。
我在训练时经常把这套模板拆给学生，先让他们单独测加法函数，再测回文判断，最后组合。任何一个函数都能独立验证，组合起来出错时也好定位。
5. 我重做这道题时踩过的坑，以及自查清单
5.1 最隐蔽的坑：循环少判了一步
我第一次写的时候用的是while (step < 30)，循环里先加再判断：
while (step < 30) { M = add(M, rev(M)); step++; if (isPal(M)) { ... } }这样有两个问题：一是初始M本身是回文数时，会先加一次再判断，导致答案从STEP=0变成STEP=1；二是某个数据如果恰好需要30步加法，最后一次加法在step=29到step=30之间完成，加法完成后循环条件step < 30已经为假，根本不会执行isPal判断，结果输出Impossible!，但正确答案是STEP=30。
改成for (int step = 0; step <= 30; step++)，每次先判断，再决定是否继续加，问题就消失了。
5.2 最高位进位的坑
写add函数时，如果while条件忘加|| carry，遇到类似999+999的数据，结果会变成998而不是1998。虽然在回文数题目里不一定出现这种极端数据，但评测数据完全可能覆盖。处理办法是while循环条件里包含carry，或者在循环结束后单独判断carry是否为1。我推荐前者，更通用，以后做其他高精度题也安全。
5.3 16进制字母转换的坑
最初写val函数时只处理了'0'到'9'，结果遇到N=16、M=A时，返回一个奇怪的数甚至负数。后来老老实实补上字母分支。给新手一个建议：进制字符串相关的题目，先把字符转换函数写好并单独测试，再写主逻辑。它们一旦出错，样例可能都过不了。
5.4 前导零的问题
有人会担心，相加后结果最高位如果是0，会不会生成“0123”这种字符串？实际上在本题的合法数据里不会出现，因为M的首位不为0，倒序数的首位是M的末位，两个最高位相加至少为1，最高位不可能是0。但如果以后做更通用的高精度函数，可以在最后加一步去前导零，保证健壮性。
5.5 我现在的自查清单
每次提交前，我都会对照这份清单检查一遍：
- 初始M是不是回文？如果是，必须输出STEP=0。
- 第30步加法完成后，有没有再做一次回文判断？
- 最高位如果有进位，有没有写进结果串？
- A-F的字符转换是否覆盖了大小写？
- 有没有把“判断回文”和“取反转串”搞混，导致原串被意外反转？
- 输出格式是不是
STEP=数字，等号旁边有没有多余空格？Impossible!后面的感叹号有没有漏掉？
这些细节在题目要求里写得清清楚楚，但恰恰是丢分最多的地方。
5.6 一点个人体会
我平时带训练时，经常让学员先不看代码，用自己的话把“N进制高精度加法”的竖式过程写一遍，再动手写代码。回文数这道题真正考察的不是“你会不会判断回文数”，而是你能不能把竖式加法、进制转换、回文判断三件事干净地组合在一起，并且在30步边界条件下不犯低级错误。
最后分享一个调试技巧：在循环里临时打印M和step，用样例数据跑一遍，观察数字长度变化是否合理。如果某一步字符串长度突然减少，或者出现了超出当前进制的字符，比如N=10时出现字母，那多半是字符转换写错了。排查完把打印语句删掉，再提交就很稳。这道题虽然年头久，但作为高精度入门的“试金石”，值得反复做几遍。
