自动搬运

查看原文

来自洛谷，原作者为

	LiWenX 4587

搬运于2025-08-24 23:17:49，当前版本为作者最后更新于2025-06-10 12:05:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

他这个题意里面的循环就是置换环，你要存在一个长度为 $A$ 和一个长度为 $B$ 的置换环使得 $A$ 中元素小于 $B$ 中元素。

比较元素的大小比较难以理解，所以可以值域和下标交换，答案显然不变，问题变成你要存在一个长度为 $A$ 和一个长度为 $B$ 的置换环使得 $A$ 中所有元素在 $B$ 中所有元素之前出现。

所以可以认为是我们要把至少一个长度为 $A$ 的置换环放到至少一个长度为 $B$ 的置换环前面，这样的限制像直接告诉你了要容斥。

所以钦定 $i$ 个长度为 $A$，$j$ 个长度为 $B$ 的置换环出来，且认为 $i$ 个环在 $j$ 个环前面，前 $i$ 个环和后 $j$ 个环内部两两不区分顺序，容斥系数就是 $(-1)^{i+j}$，设 $i$ 个长度为 $A$ 的环的方案数是 $f_i$，$j$ 个长度为 $B$ 的环的方案数是 $g_j$，剩下的数随便放都行，那么此时对答案的贡献就是 $(-1)^{i+j}f_ig_j\binom{n}{Ai+Bj}(n-Ai-Bj)!=(-1)^{i+j}f_ig_j\dfrac{n!}{(Ai+Bj)!}$。

所以如果可以计算 $f_i$，就可以使用卷积快速计算出答案。

计算 $f$ 也是简单的，长度为 $A$ 的置换环数量是 $(A-1)!$，考虑带上标号，最后外面乘上 $(Ai)!$，贡献就是 $\dfrac{1}{A}$，注意环之间不区分顺序，所以 $f_i=\dfrac{(Ai)!}{i!A^i}$，$g_i$ 同理。

求出来卷一下就做完了，时间复杂度 $O(n\log n)$，代码太过于简单就不放了。

upd：

有同学说这个容斥有点抽象，不能理解为啥是对的，那么简单证一下。

容斥系数看作是 $(-1)^{i-1}(-1)^{j-1}$，其实形式非常像子集反演：$\sum\limits_{T\subseteq S,|T|>0} (-1)^{|T|+1}=1$。

而我们要说明这个容斥是对的，那就是说对于所有的合法排列，他最后容斥系数和为 $1$，不合法排列容斥系数为 $0$。

首先不合法排列没有考虑过，所以系数当然是 $0$。

对于合法，相信你看到上面的式子你就会了，我们其实干的就是一模一样的事情，只不过是枚举了两个集合，然后计算了类似 $\sum\limits_{T_1\subseteq S_1,|T_1|>0} (-1)^{|T_2|+1}\sum\limits_{T_2\subseteq S_2,|T_2|>0} (-1)^{|T_2|+1}=1$ 的东西，唯一的限制是说 $T_1$ 里面的环都在 $T_2$ 前面。我们考虑减去不合法的贡献，如果我们考虑这个式子里面的空集，那么一个元素是不合法的集合和去掉这个元素的集合形成双射，不合法的贡献必然是 $0$，所以加上限制的式子容斥系数和依然是 $1$。

所以这个容斥是对的。