AGC019E Shuffle and Swap

题意：给出两个长度为 的 串 。

两个串均恰有 个 。令 分别表示 中所有 出现的位置。

将 和 等概率随机打乱，按 的顺序交换 和。

令 表示操作完成后 与 相等的概率，求 模 。

，时限 。

---

分别打乱，相当于只将 打乱，然后按照某种顺序执行交换。

将 之间连边 。

不难发现，由于每个点至多只有一个出边，也至多只有一个入边，故整张图是由若干个环和链组成。

• 考虑在给定图之后，合法的执行顺序数。

  环中的点都是 ，所以怎么交换是无所谓的。

  链条必须按照从头到尾的顺序执行，方案数唯一。

记 的位置（链的开头）个数为 ， 的位置（链的结尾）个数也为 。

最终形成的图中必有 条链。

考虑 EGF 计数，将各个子结构标号归并。

交换也可以利用归并处理，但不这么考虑。共有 步交换，先默认交换方案数为 ，对于一条长为 （边数）的链，将方案数除以 。（考虑为额外加权）

（这样，我们的 EGF 就是只处理标号的经典 EGF）

链的开头结尾两类点在标号分配上不是自由的，故最后再考虑他们。先考虑自由拼接的一入度一出度的点。

对于一条长度为 的链，有 个自由点，连接方案数为 ，边数为 ，构造的生成函数为 。

对于一个大小为 的环，有 个自由点，连接方案数为 ，构造的生成函数为 。

两者的 EGF 分别为

链的个数是确定的 个，而环的个数是不定的。

自由点的个数为 ，则我们要计算的是

然后我们要将链头链尾拼上去。 可以看做先按顺序链的起点，然后一个个往上面安中间的部分，然后将后面的部分拼上去，这一步方案数要额外乘以 。

最后乘上交换方案数中的 ，大功告成。

那么问题转化为对 计算

复杂度 。