「2018夏令营提高组」错排

题目链接

题意

在一个序列 $A$ 中，若 $A_i$ 的值为 $i$，则称 $i$ 为稳定的。

求恰好有 $m$ 个数稳定的长度为 $n$ 的排列个数。

$T\leq500000,n,m\leq10^6$

思路

一个有 $n$ 个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。

令 $D_n$ 表示 $n$ 个元素错排方案数。

1. 将第 $1$ 个元素放在不为 $1$ 的任意位置（记为 $k$），有 $(n-1)$ 种放置方法。
2. 放置第 $k$ 个元素：
   1.把它放在位置 $1$，此时对于 $1$ 有 $(n-1)$ 种放置方法，对于剩下的 $(n-2)$ 个元素有 $D_{n-2}$ 种放置方法；
   2.不把它放在位置 $1$，则第 $1$ 个位置有 $(n-1)$ 种放法，此时可以把第 $k$ 个元素看作第 $1$ 个，对于剩下的 $(n-1)$ 个元素，共有 $D_{n-1}$ 种放置方法。

得到错排公式的递推式：

$\begin{aligned} D_1&=0\\ D_2&=1\\ D_n&=(n-1)\cdot(D_{n-2}+D_{n-1}) \end{aligned}$

本题显然是求 $C^m_n\cdot D_{n-m}$。

实现

预处理出 $1-n$ 的阶乘及其逆元，可在 $O(1)$ 时间内求出组合数。

利用错排公式的递推式预处理出 $D_n$。

代码

#include<cstdio>
using namespace std;
const int mod=1e9+7;
int t,n,m;
long long fac[1000001],inv[1000001],d[1000001];
inline long long pow(long long a,int tim)
{
    long long res=1;
    while(tim) {
        if(tim&1) {
            res=res*a%mod;
        }
        a=a*a%mod,tim>>=1;
    }
    return res;
}
int main()
{
    freopen("permutation.in","r",stdin);
    freopen("permutation.out","w",stdout);
    fac[0]=1;
    for(int i=1;i<=1000000;++i) {
        fac[i]=fac[i-1]*i%mod;
        inv[i]=pow(fac[i],mod-2);
    }
    d[1]=0,d[2]=1;
    for(int i=3;i<=1000000;++i) {
        d[i]=(i-1)*(d[i-2]+d[i-1])%mod;
    }
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        printf("%lld\n",n==m?1ll:(m==0?d[n]:fac[n]*inv[m]%mod*inv[n-m]%mod*d[n-m]%mod));
    }
    return 0;
}