P6998

zhylj · 2022-01-15 10:06:29 · 题解

先考虑树的情况怎么做：一个经典套路是先找到重心（如果有两个重心并且以两个重心为根时的树同构，那么答案再 \times 2），然后把重心定为根，问题就被转化为了有根树，那么对于一个节点，可以把它的孩子中每个同构等价类的大小的阶乘乘起来贡献到答案。同构可以考虑通过树哈希来判断，即每个深度 i 用一个哈希函数 h_i(a)=\sum_j (a_j+1)b_i^j\bmod p，其中 b_i 为随机数，p 为你喜爱的质数，a_i 为所有孩子哈希值排完序后的结果。

接着考虑仙人掌，可以发现仙人掌同构等价于圆方树同构，于是先求圆方树并找到重心，然后从重心开始 DFS（注意到由于重心那一侧），分类讨论：

• 对于方点，若其为重心，那么它可以旋转，也可以翻折，我们要找出环上哈希值构成的序列（必须按照环的顺序）和它的反串的所有循环同构和原串相同的个数 c，那么它对答案贡献 \times c。
• 对于非重心方点，其父亲所在子树（也就是重心所在子树）的大小超过了 \left\lfloor \dfrac n2\right\rfloor，所以这个环必然不可能被旋转，但它依然可以翻折，所以若它是回文，那么对答案贡献 \times 2。
• 否则，依然根据孩子中同构的等价类大小的阶乘来对答案贡献。

需要注意的是，由于环可以翻折，但不能旋转，所以我们维护非重心方点的哈希值时，取的是孩子哈希值序列（注意我们必须按环的顺序排列这个序列）和它反串中字典序最小的一个来做哈希。

然后统计答案的时候不难发现是若干个阶乘之积，维护出每个阶乘的贡献然后做一个前缀和，对每个质数暴力统计就好了。

时间复杂度 \mathcal O(n\log n)。

代码链接（写的较丑，谨慎参考）。