自动搬运

查看原文

来自洛谷，原作者为

	ikunTLE 互关条件见主页（luogu.me/paste/1ij66blw），关注我可以获得我小号 OIerDb 的关注（需私信） || 最后在线时间：2025年8月24日22时48分

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

注意事项：

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