自动搬运

查看原文

来自洛谷，原作者为

	Aurelia_Veil 学术+全关私信|半退犇退TC半退谷|刷分号|必须蓝勾|目标估值325，目标等级分1500|六年级小学生初来乍到，互关私信咩|一只小dongdong，飞入花丛中~|不知道为什么运气很好的小dongdong

搬运于2025-08-24 23:11:18，当前版本为作者最后更新于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}$。

四、代码讲解

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

感谢观看咩～