【题解】CF1768E Partial Sorting

ExplodingKonjac · 2023-01-07 22:03:24 · 题解

【原题链接】

2023/10/7 upd: 修复了式子的错误。

题目分析

首先，使用三次操作即可将序列排序：1,2,1。其中第一次操作把前 2n 个中最大的 n 个放到了 [n+1,2n]，于是第二次操作就能够把整个序列最大的 n 个放到 [2n+1,3n]，最后一次操作把 [1,2n] 排序。（当然 2,1,2 也可行）

考虑需要不同操作次数的方案：

操作次数 \le0：

有方案数 s_o=1。
操作次数 \le1：

说明 [1,n] 已经归位或者 [2n+1,3n] 已经归位。用前 n 个固定的方案数加后 n 个固定的方案数，减去两边都固定的方案数，则有
s_1=2(2n)!-n!
操作次数 \le2：

这里需要一些分析。我们发现，需要至多两次操作的情况形如：第一次 1 操作把 1,2,\dots,n 都放在了 [1,2]，然后排序一次；也可以是第一次 2 操作把 2n+1,2n+2,\dots,3n 都放在了 [2n+1,3n]。也就是说，1,2,\dots,n 全部在 [1,nn] 内。或者 2n+1,2n+2,\dots,3n 全部在 [2n+1,3n] 内。可以发现这就是充要条件。

然后考虑计数，用 1,2,\dots,n 满足条件的方案，加上 2n+1,2n+2,\dots,3n 满足条件的方案，再减去都满足条件的方案。前两者的方案是相同的，可以得到是 \displaystyle\binom{2n}{n}n!(2n)!。至于后者，因为 [1,2n] 和 [n+1,3n] 有交 [n+1,2n]，因此可以枚举 2n+1,2n+2,\dots,3n 落在 [n+1,2n] 的个数，最终得到：
s_2=2\binom{2n}{n}n!(2n!)-\sum_{i=0}^n \binom{n}{i}\binom{n}{n-i}\binom{2n-i}{n}(n!)^3
操作次数 \le3：
s_3=n!

那么最后答案就可以算了，注意我们算的是小于等于的方案数，需要差分一次。

ans=1(s_1-s_0)+2(s_2-s_1)+3(s_3-s_2)

代码实现

#include <bits/stdc++.h>
using namespace std;

// 快读

using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;

int MOD;
inline int qpow(LL a,LL b) { int r=1;for(;b;(b&1)?r=r*a%MOD:0,a=a*a%MOD,b>>=1);return r; }
inline int madd(int x) { return x; }
inline int mmul(int x) { return x; }
inline int msub(int x,int y) { return (x-=y)<0?x+=MOD:x; }
inline int mdiv(int x,int y) { return (LL)x*qpow(y,MOD-2)%MOD; }
template<typename ...Args>inline int madd(int x,Args ...y) { return (x+=madd(y...))>=MOD?x-=MOD:x; }
template<typename ...Args>inline int mmul(int x,Args ...y) { return (LL)x*mmul(y...)%MOD; }

int n,fac[3000005],inv[3000005];
inline int binom(int r,int c) { return mmul(fac[r],inv[c],inv[r-c]); }
int main()
{
    qin>>n>>MOD;
    fac[0]=1;
    for(int i=1;i<=3*n;i++) fac[i]=mmul(fac[i-1],i);
    inv[3*n]=qpow(fac[3*n],MOD-2);
    for(int i=3*n;i>=1;i--) inv[i-1]=mmul(inv[i],i);
    int s1=msub(madd(fac[2*n],fac[2*n]),fac[n]);
    int s2=mmul(2,binom(2*n,n),fac[n],fac[2*n]);
    int s3=fac[3*n];
    for(int i=0;i<=n;i++) s2=msub(s2,mmul(binom(n,i),binom(n,n-i),binom(2*n-i,n),fac[n],fac[n],fac[n]));
    s3=msub(s3,s2),s2=msub(s2,s1),s1=msub(s1,1);
    qout<<madd(s1,mmul(s2,2),mmul(s3,3));
    return 0;
}