ARC060D Best Representation

题意：若一个串不是整循环串，称之为好串。

给出一个字符串 。

求出 的“好串拆分”的最小段数。以及段数最小前提下的方案数（对 取模）。

，时限 。

---

如果这不是个 ARC 题，咋一看确实挺唬人的……

• 若 中只有一种字符，则只能拆分为 段，每段一个字符。

• 若 本身为好串，则保留本身。

接下来只需要考虑 是整循环串的情况。

此时可以发现，最小段数一定是 。

• 证明：

  • 结论：对于周期 的整循环串 ，拿去最后一个字符后，一定不是整循环串。

  于是，我们将 切分为 即可构造两段的方案。

  下面是结论的证明：

  记 的最小正循环节为 ，记 ，且 的最小整循环节为 。

  由于 之中必有一个是奇数，不难证明 。

  于是，根据弱周期引理， 是 的周期，显然，也是整周期。

  由于 是 的最小整周期，则必有 。

  我们知道 ，故 。

  另一方面，显然有 ，故 。

  这说明 都是同一个字符。由于整个串不都是同一个字符，故 必然是不同的字符。

  此时 必然不是整循环串，矛盾。

然后我们只需要枚举每种切分，并判断每个 前/后 缀是否为正循环串即可。

• 结论：对于整循环串 ， 的最小周期同时也是 的最小整周期。

那么，我们使用 求出 的每个 前/后 缀的最小周期，即可得知答案。

复杂度 。（模数是来开玩笑的啦）