ARC064D Rotated Palindromes

题意：首先生成一个长度为 ，字符集为 的回文串 。

然后，进行任意次以下操作：

• 把 中的第一个元素移到最后。

经过这些步骤，一共可以得到多少种不同的数列 呢？答案对 取模。

，时限 。

---

我们发现，操作等价于进行循环移位。

考察回文串与循环移位之间的映射。

一个最小整周期为 的回文串 能对应 个本质不同的循环移位后的串 。

再考虑反映射，我们发现，当 为奇数时，一个 只会对应一个 ，当 为偶数时，一个 恰好会对应两个 。

如 的最小整周期都是 ，它们对应的 是相同的。

（另一种思路是，发现两个 对应的 要么完全相同，要么无交集。故只需要统计循环移位下本质不同的 的个数，容易发现 为偶数时等价类大小总是 ，为奇数时则总是 ）

于是，枚举 计算答案 :

其中 是最小整周期为 的回文串个数。

---

一个长度为 的回文串方案数为 ，但如此随意生成的回文串可能有更小的整周期（是长度的因数）。

考虑莫比乌斯反演，设 为最小整周期是 的因数的方案数。

则有：

暴力计算，复杂度为 ，可以通过。

注意到 只在 中无平方因子时有值， 的枚举可以简化。