洛谷——P4071 [SDOI2016]排列计数（错排+组合数学）

P4071 [SDOI2016]排列计数

求有多少种长度为 n 的序列 A，满足以下条件：

1 ~ n 这 n 个数在序列中各出现了一次

若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的

满足条件的序列可能很多，序列数对 $10^9+7$取模。

显然此题的答案就是$C(n,m)*d[n-m]$

求解组合数$C(n,m)$使用通项公式$\frac{n!}{m!\times (n-m)!}$

由于$n,m$很大，所以要预处理出$n!$

由于$10^9+7$是个质数，所以根据费马小定理求逆元

错排公式 $d_n=(n-1)*(d_{n-1}+d_{n-2})$

$d_1=0,d_2=1$

推导方法：

错排吗，每一个数都不在其原来的位置上

1.假设把$n$放在$k$（$k<n$）上，那么就有$n-1$种方法

2.考虑放$k$，若把$k$放在位置$n$上，有$d_{n-2}$，反之有$d_{n-1}$种方法

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#define LL long long

#define N 1000005

#define mod (LL)1000000007

using namespace std;

LL d[N],T,inv[N],f[N];

LL pow(LL a,LL b){

    LL s=;

    for(;b;b>>=,a=a*a%mod)

        if(b&) s=s*a%mod;

    return s;

}

LL C(LL n,LL m){

    LL del=(inv[m]%mod*inv[n-m]%mod)%mod;

    LL x;

    if(del<=N-) x=inv[n]*f[del]%mod;

    else x=inv[n]*pow(del,mod-)%mod;

    return (x%mod+mod)%mod;

}

int main()

{

    scanf("%lld",&T);

    d[]=,d[]=;

    for(int i=;i<=N-;i++) d[i]=(((i-)%mod)*(d[i-]+d[i-])%mod)%mod;

    inv[]=;

    for(int i=;i<=N-;i++) inv[i]=inv[i-]*i%mod;

    f[]=;

    for(int i=;i<=N-;i++) f[i]=(mod-mod/i)*f[mod%i]%mod;

    while(T--){

        LL n,m;

        scanf("%lld%lld",&n,&m);

        if(n==m) printf("1\n");

        else printf("%lld\n",C(n,m)*d[n-m]%mod);

    }

    return ;

}

~~蒟蒻（博主）又刷了一道水题。。。~~