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\) 个空格，并在空格内全排列。
  因此重复部分的方案数为 \[ \sum_{i=1}^{n}\binom{n}{i}\binom{n}{n-i}\binom{2n-i}{n}(n!)^3 \]
综合以上分析可知： \[ \mathrm{Ans}_2= \left(2 \times \binom{2n}{n}\times n!\times (2n)!\right) -\left(\sum_{i=1}^{n}\binom{n}{i}\binom{n}{n-i}\binom{2n-i}{n}(n!)^3\right)-\mathrm{Ans}_0-\mathrm{Ans}_1 \]
\(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;
}