P9554 题解

ikunTLE · 2024-06-12 17:15:40 · 题解

题目传送门

思路

既然题目中有关于 n=1 的特判，那么我们不难发现，当 n=1 时，从 0 到 m+1 中有 m+2 种不同的方案。

其他情况，要根据是否回文分为两种情况：

1. 不回文。前后都是 m+1 种，中间 m 种，总和是 (m+1)^2m^{n-2} 种。

2. 回文。前一半和不回文的情况一致，但是后半段却因回文已经确定了，答案需要在不回文的情况下 \times\lceil\frac{n}{2}\rceil。

注意事项：

• 注意每一步计算都要取模。
• 容易超时，建议用快速幂。