题解：P11909 [NHSPC 2023] H. 整数的回文分解法

Aurelia_Veil · 2025-04-11 19:12:12 · 题解

题解：P11909 [NHSPC 2023] H. 整数的回文分解法。

题目传送门：in

一、本题拆解：

本题要求我们求出 N 的拆分成若干个数，并且要求拆分后为回文数，求出总共的拆分种类数。

二、思路拆分：

1. 回文

因为最终结果要求是回文数，所以可以只保留前面 \lfloor \frac{N}{2} \rfloor 个数。

2. 拆分

既然是拆分，我们可以反向思考，把拆分转换成合并，也就是将 \lfloor \frac{N}{2} \rfloor 个 1 合并成其他数列，那这样每个数就有两种合并方式：

• 不合并。
• 与后面一个数合并。

三、结论

既然每个数有两种合并方式，最终答案就为 2^{\lfloor \frac{N}{2} \rfloor}。

四、代码讲解

我们可以选择快速幂快速的解决此公式，得到答案。

感谢观看咩～