题解：P12735 回报

· · 题解

他这个题意里面的循环就是置换环，你要存在一个长度为 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。

所以这个容斥是对的。