ARC077D

题意 ： 对于非空串 ，定义 是在 后面添加一些（至少一个）字符得到的最短平方串。

现在给出平方串 ，记 （可以认为有无穷多个 ）

给出 ，询问 中各个字符的出现次数。（字符集为小写英文字母）

，，时限 。

---

考虑给出 如何求解 。

设 的周期集合为 ，求出 ，即大于一半的最小循环节。

将 补成两个 即可。

记 的最短循环节前缀 为 ， 所对应的串即为 。记 为 的最小循环节前缀。

也即：。

由于会重复无限次操作，我们只需考虑前半部分，即 。

观察这一操作有何规律，能发现：

• 为整循环节。

  的最小循环节与 的相同，且也是整循环节。

  记 ，操作的效果为： 容易在 内求解。

• 不是整循环节。

  的最小循环节为 ，且也不是整循环节。

  证明：假设 有小于 的周期 。

  注意到 同时也是 的周期，则有 。

  考虑 ，由于 是 的前缀，又有 。

  根据周期有 ，由于 ，此时 已经是 的一部分。

  根据 的周期 ，又有 即 。

  那么，由于 ，有 。

  根据弱周期引理， 有新的周期 。

  由于 已经是最小周期，故 一定是 的倍数。（否则会得到更小的周期）

  注意到 ，矛盾。

  记 ，操作的效果为： （记第 此操作后的串为 ，有 ）

  串的长度是指数增加的，不难做到 。

  还需用一次 的 求出 。