CF1768E Partial Sorting 题解

题意：

给定整数 $n$ 和质数 $M$。

对于一个 $1\sim 3n$ 的排列 $p$，你可以进行下列操作：

将 $p$ 的前 $2n$ 个元素从小到大排序。

将 $p$ 的后 $2n$ 个元素从小到大排序。

可以证明任意 $1\sim 3n$ 的排列都能通过若干次上述操作从小到大排序。

记 $f(p)$ 表示将 $p$ 从小到大排序所需的最小总操作次数。

你需要求出对于所有 $1\sim 3n$ 的排列 $p$，其 $f(p)$ 总和对 $M$ 取模后的值。

输入格式：

输入一行两个整数 $n,M(1\leq n\leq10^6;10^8\leq M\leq10^9)$，保证 $M$ 是质数。

输出格式：

输出一行一个整数表示 $f(p)$ 的总和对 $M$ 取模后的值。

一个显然的操作上界是 $3$ 次。下面我们来依次考虑 $f(p)$ 的取值：

$f(p) \le 0$ ，即 $f(p) = 0$ 。这种情况只有一种，答案为 $1$
$\mathrm{Ans}_0 = 1$
$f(p) \le 1$ 。

这种情况对应：前 $n$ 个数字，或后 $n$ 个数字已经在正确位置上了。

计算方法：对前 $2n$ 或后 $2n$ 全排列，去掉两侧有序时重复计算的部分，也就是中间的全排列
$\mathrm{Ans}_1 = 2\times (2n)! - n! - \mathrm{Ans}_0$
注：我们用 $\mathrm{Ans}_k$ 表示 $f(p) = k$ 的答案，但是讨论 $f(p) \le k$ 的方案，这样更方便一些。
$f(p) \le 2$ 。

这种情况对应：最小的 $n$ 个元素在 $[1,2n]$ 分布，或最大的 $n$ 个元素在 $[n+1,3n]$ 分布。（可同时满足）

计算方法：考虑先分别计算两侧的答案，然后去掉重复部分：
- 两侧的计算：在 $2n$ 中选 $n$ 个位置排列这最小的 $n$ 个元素，剩下的自由排列，有两种情况
  $2 \times \binom{2n}{n}\times n!\times (2n)!$
- 重复部分的计算：（不妨考虑去掉右侧的「与左侧重复计算的部分」）
  
  首先要明确什么情况会重复：最大的 $n$ 个数和最小的 $n$ 个数在 $[n+1,2n]$ 均有分布。
  
  考虑枚举有 $i(0\le i\le n)$ 个「最大的 $n$ 个数」分布在 $[n+1,2n]$ 中：
  - 有 $i$ 个数分布在 $[n+1,2n]$ 中，对应方案数：$\binom{n}{i}\times n!$ （注： $n!$ 是对最大的 $n$ 个数的排列）
  - 有 $n-i$ 个数分布在 $[2n+1,3n]$ 中，对应方案数 $\binom{n}{n-i}\times n!$
  - 此时 $[1,2n]$ 还有 $2n-i$ 个空位，自由放最小的 $n$ 个数，对应方案数： $\binom{2n-i}{n}\times n!$
    
    这个时候我们不用要求 $n$ 一定在 $[n+1,2n]$ 中，思考一下可以发现不要求的情况也会被左侧算到。
    
    并且这个时候方案数右侧的 $n!$ 表示的是在 $2n-i$ 个位置中选 $n$ 个空格，并在空格内全排列。
  因此重复部分的方案数为
综合以上分析可知：
$f(p) \le 3$ 。

这种情况对应「所有情况」，因为显然上界是 $3$ 。

$f(p)=3$ 其实就是 $f(p)\le 2$ 剩下的一些情况，但是基本都有例如「最大的 $n$ 个数在 $[1,n]$ 有分布」的特点
$\mathrm{Ans}_3 = (3n)! - \mathrm{Ans}_0-\mathrm{Ans}_1-\mathrm{Ans}_2$

最后我们的答案就是 $\sum_{0\le k\le 3} k\times \mathrm{Ans}_k$

时间复杂度 $\mathcal{O}(3n)$ ，主要是预处理组合数。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e6 + 55))

int mod,ans[5],fac[N],inv[N];
int mul(int cnt, ...)
{
    int res = 1; va_list ptr; va_start(ptr, cnt);
    for(int i = 0; i < cnt; i++) {
        res = res * va_arg(ptr, int) % mod;
    }   va_end(ptr);
    return res;
}
int C(int n,int m)
{ 
    if(n < m) return 0;
    return mul(3, fac[n], inv[n - m], inv[m]);
}
int qpow(int a,int b,int c=1)
{
    for(a %= mod; b; b >>= 1) {
        if(b & 1) c = c * a % mod;
        a = a * a % mod;
    }
    return c;
}
void init(int len)
{
    fac[0] = 1; inv[0] = 1;
    for(int i = 1; i <= len; i++) fac[i] = fac[i - 1] * i % mod;
    inv[len] = qpow(fac[len], mod - 2);
    for(int i = len - 1; i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n >> mod; init(3 * n + 10); ans[0] = 1;
    ans[1] = ((2 * fac[2 * n] - fac[n] - ans[0]) % mod + mod) % mod;
    ans[2] = mul(4, fac[2 * n], C(2 * n, n), 2ll, fac[n]);
    for(int i = 0; i <= n; i++)
    {
        int tmp = mul(3, C(n, i), C(n, n - i), C(2 * n - i, n));
        tmp = mul(4, tmp, fac[n], fac[n], fac[n]);
        ans[2] = (ans[2] - tmp + mod) % mod;
    }
    ans[2] = ((ans[2] - ans[1] - ans[0] + mod) % mod + mod) % mod;
    ans[3] = ((fac[3 * n] - ans[2] - ans[1] - ans[0]) % mod + mod) % mod;
    int res = 0;
    for(int i = 0; i < 4; i++) { 
        res = (res + i * ans[i]) % mod;
    }
    cout << res << '\n';
    return 0;
}