题解：P10101 [ROIR 2023 Day 2] 一个普通的字符串问题

_lbw_ · 2024-07-13 21:09:01 · 题解

对于相邻的字符 s_i,s_{i+1}，连边 s_i\to s_{i+1}。

也就是说，我们要求在这张点数为 3 的图上走一条欧拉路径，对点区分的方案数。

对于欧拉相关记数，考虑 BEST 定理。

但有两个问题：

• BEST 定理是对边区分的。
• BEST 定理是欧拉回路。

首先我们处理区分方式不同的问题，考虑求欧拉路径对边区分的方案数，这个问题除以每条重边次数的阶乘即为原问题的答案。

然后处理回路，枚举起点和终点，从终点向起点连一条边，我们发现因为 BEST 定理是对边区分且循环同构，我们把每一种方案旋转，使得我们新加那条边在最后即可。

所以此时直接套用 BEST 定理公式即可，点数较少可以手动求外向树。

实现时注意图不一定取满 3 个点。

时间复杂度 \mathcal{O}(L+q|\sum|^5)，代码。