自动搬运

查看原文

来自洛谷，原作者为

	lbw 若有 笃信之物 莫忘厮守

搬运于2025-08-24 22:54:40，当前版本为作者最后更新于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)$，代码。