CF1768E Partial Sorting 题解

感觉比较像 sale（？但是要简单一些

可以证明对于任意一个排列都最多只需要三次操作使得排列变得满足条件。因此考虑分别计数需要 $0,1,2,3$ 次操作可以排序的排列数量：

• 需要 $0$ 次操作的排列数量：显然答案就是 $1$。
• 需要 $1$ 次操作的排列数量：显然这次操作只能把前 $2n$ 个数排序或把后 $2n$ 个数排序，因此需要不超过 $1$ 次操作的排列数量可以被表示为前 $n$ 个数正好是 $1,2,3,\ldots,n$ 或后 $n$ 个数正好是 $2n+1,2n+2,\ldots,3n$ 的排列数量，简单容斥可得答案为 $2(2n)!-n!$。
• 需要 $2$ 次操作的排列数量：显然此时排列要么 $1\sim n$ 元素在前 $2n$ 个位置，要么 $2n+1\sim 3n$ 元素在后 $2n$ 个位置。对于需要不超过 $2$ 次操作的排列数量，若假设两个条件互斥，则显然答案可以被计数为 $2(2n)!n!\binom{2n}n$。然后考虑容斥，计数同时满足前面给出的两个条件的排列数目。容易想到枚举出现在中间区间里数的情况。这里枚举 $i$ 表示恰好有 $i$ 个数值在 $[n+1,2n]$ 范围内出现在序列的前 $n$ 个位置。那么可以这样计数：
  • 前 $n$ 个位置里有 $i$ 个数字在 $[1,n]$ 范围内，方案数是 $n!\binom ni$。
  • 中 $n$ 个位置里有 $n-i$ 个数在 $[1,n]$ 范围内，方案数是 $n!\binom ni$。
  • 后 $n$ 个位置里有 $i$ 个数在 $[n+1,3n]$ 范围内，方案数是 $n!\binom{2n-i}n$。
• 直接乘法原理乘起来计数即可。
• 需要 $3$ 次操作的排列数量：直接用排列数量 $(3n)!$ 减去需要 $0,1,2$ 次操作的排列数量即可。

该算法总时间复杂度为 $O(n)$，可以通过该题。