CF715E Complete the Permutations

发表于 2025-03-13 分类于算法竞赛，题， Codeforces 阅读次数：

题意：定义两个排列的距离为：让两个排列变得相同，在第一个上所需交换的次数。

现在给出两个长度为的排列，某些位置为表示未确定，现在求两个排列距离为的方案数。

答案对取模，，时限。

发现自己对于输入大于的数数题不那么在行，于是来做做这个题。

先考虑两个已经确定的排列之间的距离。

结论：视作置换， $环的个数$ 即为距离。
证明：
- 构造：只要把每个环适当旋转一步，就能得到正确的排列。而旋转一个大小为的环只需要次交换（对单个环达到下界），总交换次数就是 $环的个数$ 。
- 下界：可以证明，跨越两个环的交换是不优的，因为这打破了环的封闭性。

在一个不确定的置换中，我们会产生类边（链）：

对于第一种，我们可以简单地把标号传递（可以使用并查集），然后忽略这些边。如果已经形成环就记下。

此外，如果一组中，则合成链。

记处理后 ②③④ 三种链的个数分别为。

我们以三步将不完整的置换填写为完整的置换：

此外，还要考虑成环的总个数，若成个环，则加权。最终得到的幂级数即为答案。

观察发现，接上还是得到。

而接上还是得到。

所以，只要不成环（在第三步之前），④ 类边的个数是不变的。

而 ②③ 类边之间不会转化，这就说明三步之间是独立的。分别考虑三步的幂级数。

意思是，先选出条链拼成个环，然后把剩下 ② 类链转化为 ④ 类链。

这转化是有讲究的，我们不能再形成环，又要不留 ② 类边，只能串成若干条以开头的链。

对于第一条待处理的 ② 类边，有种连法，可以连到其他 ② 类边，或者 ④ 类边。

连完之后就会消失，所以下一条边少了一种方案，呈现出来就是下降幂。

考虑 ③ 类边内部获得个环的方案数。和上面差不多。记为。

最后考虑 ④ 类边内部获得个环的方案数。

额外的是因为我们可以在原排列上以任意顺序填写这些边。

把三个数组卷积即可。

此题的较小。允许我们递推第一类斯特林数以及暴力卷积。