CF1768E Partial Sorting

· · 题解

可能更好的阅读体验

题目传送门

题目翻译

UPD：组合数上下打反了 /youl，已经更正。

题目解析

显然我们可以证明 f(p)\in\{0,1,2,3\}

考虑 $f(p)=1

如果前面交换一次，那么有 (2n)! 种。只交换后面同理。
考虑交换前后都可以的重复情况，那么就是 n! 种。
容斥得 s_2=2\times(2n)!-n!

考虑 f(p)=2
如果前面交换一次然后后面交换，那么只需要保证 1\sim n 全部在 1\sim 2n 位置内。方案数是

\binom{2n}{n}\times(2n)!

如果是先交换后面同理。
考虑重复的情况，也就是 1\sim n 全部在 1\sim 2n 位置，并且 2n+1\sim 3n 全部在 n+1\sim 3n 位置。
枚举 1\sim n 在 n+1\sim 2n 位置内的数量，可以得到重复的方案为

M=\sum_{i=0}^{n}\binom{n}{i}\binom{n}{n-i}\binom{2n-i}{n}\times (n!)^3

所以

s_3=2\times\binom{2n}{n}\times(2n)!-M f(p)=3$ 直接用来减就好了，$s_4=(3n)!-s_1-s_2-s_3

答案就是 s_2+2s_3=3s_4

int n,MOD; ll fact[maxn],inv[maxn],s1,s2,s3,s4,M;
ll fastpow(ll x,ll y){
    ll tmp=x%MOD,res=1;
    while(y){
        if(y&1) res=res*tmp%MOD;
        y>>=1; tmp=tmp*tmp%MOD;
    } return res;
}
#define P(n,m) (fact[n]*inv[(n)-(m)]%MOD)
#define C(n,m) (fact[n]*inv[m]%MOD*inv[(n)-(m)]%MOD)
int main(){
    n=read(); MOD=read(); int i; fact[0]=1; for(i=1;i<=n*3;i++) fact[i]=fact[i-1]*i%MOD;
    inv[2*n]=fastpow(fact[2*n],MOD-2); for(i=n*2-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%MOD;
    s1=1; s2=2*fact[2*n]-fact[n]+MOD-1; s2%=MOD;
    M=0; for(i=0;i<=n;i++) M+=C(n,i)*C(n,n-i)%MOD*P(2*n-i,n)%MOD,M%=MOD;
    M*=fact[n]*fact[n]%MOD,M%=MOD;
    s3=2*P(2*n,n)*fact[2*n]%MOD-M-(s1+s2); s3%=MOD,s3+=MOD,s3%=MOD;
    s4=fact[3*n]-s1-s2-s3; s4%=MOD,s4+=MOD,s4%=MOD;
    print((s2+s3*2+s4*3)%MOD); return 0;
}