CF1768E

· · 题解

显然我们最多只需要 3 次操作：操作 1\to 操作 2\to 操作 1。

  1. 条件：这个排列已经是有序的了。 代码： ```cpp /**** 0 ****/ ans[0] = 1; ```
  2. 条件：前 $n$ 个数字，或后 $n$ 个数字已经在正确的位置上了。 前 $2n$ 个或者后 $2n$ 个自由排列，就是 $(2n)!$。 重复的部分：就是中间的 $n$ 个元素。 答案是 $2\times (2n!)-n!$。 代码： ```cpp /**** 1 ****/ ans[1] = (2 * fac[2 * n] - fac[n] - ans[0] + mod) % mod; ```
  3. 条件：最小的 $n$ 个元素在 $[1,2n]$，或最大的 $n$ 个元素在 $[n+1,3n]$。 如果是前者，那么： - 有 $C^n_{2n}$ 中方案为这些数字选择 $n$ 个位置。 - 对于这个选择的位置，有 $n!$ 种方案去安排最小的 $n$ 个数，剩下的 $2n!$ 任意排列。 如果是后者，也同理。 但是，这两种情况是有交叉的。 我们来讨论一下在 $[n+1,2n]$ 这个区间内的 $n$ 个数。 如果这个区间内恰好有 $i=0$ 个数出现前面的 $n$ 个位置： - 在前 $n$ 个数字中，有 $n$ 个数字在 $[1,n]$ 范围内，有 $C^{n-0}_n\times n!$ 种情况。 - 在前 $n$ 个数字中，有 $0$ 个数字在 $[n+1,2n]$ 范围内，有 $C^0_n\times n!$ 种情况。 - 在后 $n$ 个数字中，有 $n$ 个数字在 $[n+1,3n]$ 范围内，有 $C^n_{2n-0}\times n!$ 种情况。 然后把具体的 $0$ 转化成抽象的 $i$，那么交叉就会多 $C^{n-i}_n \times C^i_n \times C^{n}_{2n-i} \times n! \times n!\times n!$。 然后在 $[1, n]$ 的范围内枚举 $i$，最终将这一部分减去。 所以答案就是 $2\times C^n_{2n}\times n!\times 2n!-\sum^n_{i=0}C^{n-i}_n\times C^{i}_{n}\times C^{n}_{2n-i}\times n!\times n!\times n!$。 ```cpp /**** 2 ****/ ans[2] = fac[2 * n] % mod * C(2 * n, n) % mod * fac[n] % mod * 2 % mod; rep (i, 0, n) { int sub = C(n, i) % mod * C(n, n - i) % mod * C(2 * n - i, n) % mod; sub = sub * fac[n] % mod * fac[n] % mod * fac[n] % mod; ans[2] = (ans[2] - sub + mod) % mod; } ans[2] = (ans[2] - ans[1] - ans[0] + mod) % mod; ```
  4. 条件：所有 $(3n)!$ 个排列。 直接用 $(3n)!$ 减去之前的情况就行。 ```cpp /**** 3 ****/ ans[3] = (fac[3 * n] - ans[2] - ans[1] - ans[0] + mod) % mod; ```

最后答案是 ans_0 \times 0 + ans_1 \times 1 + ans_2 \times 2 + ans_3 \times 3，输出即可。

代码不放了。