CF1205E Expected Value Again

题意：字符集大小为 ，问长度为 的字符串的 个数平方的期望。

答案对 取模。

，，时限 。

---

一个更简单的相关问题 : 个数的期望

从每个字符串出发考虑较为困难，不妨从每个 出发考虑。

众所周知 和周期是一一对应的，我们可以改为考虑周期。

不难发现，存在长度为 的周期的字符串总数即为 ，所以答案是 。

---

回到原问题

“ 个数平方”中，单个 的贡献不再是独立的。但是，从字符串出发分别考虑仍然很困难。

可以改而计算字符串的“ 对子”数目，这样，我们只需要考虑两个 之间的影响。

若一个字符串同时存在周期 ，相当于从 向 连边表示相等，若最终有 个等价类，方案数即为 。

考虑如何快速计算等价类个数：

先解决 的子问题。

连出 ，这将等价类限定为 个，且 各不相同。

• ① 若 ，这说明每个等价类 都有出边 。不难发现由于 ，恰好形成一个大环。

• ② 若 ，不妨设 ，此时只有 是有出边的，所以 是无出边的。

  上面提到，完整的图是一个大环，现在断掉了若干条边，则是一些链的集合。

  等价类个数 点数 边数，即 。

当 时，模 不等的位置互不影响，我们可以把问题转化成 个 互质的子问题。

• 若 ，则等价类个数为 （其实就是弱周期引理）

• 若 ，记 ，记 为一个子问题。

  转化为 个 ，以及 个 。

  若 ，则 ，此时每个子问题都为 ② 类，则总贡献为 。

  否则，若 ，则子问题 为 ① 类，贡献为 。

  子问题 为 ② 类，贡献为 。

  总贡献即为 。

综上，等价类个数可以写成统一的形式 。

则有：

---

分三部分计算：

根据 拆掉 。

• Part1

• Part2

记 。

有 。

相当于将方形截去一个角（实际上总是只剩一个角），不难 计算合法的 对数。

枚举 的复杂度为 。

• Part3

将 提出，并施以类似反演可得 :

暴力枚举 后，可行的 是一个前缀，预处理幂后不难 计算贡献。

枚举 的复杂度为 也可以不枚举 。

对于一个确定的 ，后面的贡献是一个关于 的多项式，考虑分别计算每一项的贡献系数。

相当于枚举 然后给 的贡献系数加上 。

由于 即 ，对于 ，被枚举到的次数恰为 。

（实际上，方形截角总是容易计算的）

这类修改不难用差分实现。

复杂度即为 。