错排 get ！

· · 个人记录

何为错排？

所谓错排，即错位排列，意为对于 n 个物品对应着 n 个位置，问所有物品都不在其对应位置上的排列方案数。

错排递推公式：

D_{n} = (n-1) * (D_{n-1} + D_{n-2}) D_{0} = D_{1} = 0 , D_{2} = 1

推导过程：

设现在有 n 个物品，第 n 个物品被放在 k 位置上 (k \ \ != n)

首先，1 <= k < n 所以 n 可能的方案为 n-1

然后，对于 k 来说，

如果 k 不在 n 位置上，假设 n 是 k 对应的位置，把 n 去掉后剩余的 n-1 项对于 k 来说又是一个错排，即 D_{n-1} ，

如果 k 在 n 位置上，那么去掉 k 和 n 后的 n-1 项必须是一个错排，即 D_{n-2}

由此可得递推公式。

模板:

传送门

int main(void)
{
    cin >> n;
    long long f[MAXN] = {0,0,1};
    for(int i=3;i<=n;i++)
        f[i] = (i-1)*(f[i-1]+f[i-2]);
    cout << f[n] << endl;
    return 0;
}

提高：

传送门

感觉这道题主要还是考的逆元的样子。。。（大概是我逆元学的不好？）

公式就不解释了，就是 C^{m}_{m} * D_{n-m} （一眼题）

由于数据范围巨大，递推求组合数不是 T 飞就是 M 飞，

所以需要预处理出阶乘的逆元，然后 O(1) 求组合数，顺便，错排也是可以预处理一下的。

一定要注意特判啊

int T;
int n,m;
long long ans;
long long num[MAXN],inv[MAXN]; //阶乘 及其 逆元
long long c[MAXN],d[MAXN];

long long FastPow(long long a, long long x)
{
    long long ans = 1;
    while(x)
    {
        if(x & 1) ans = ans*a%mod;
        a = a*a%mod;
        x >>= 1;
    }
    return ans;
}

void find_inv()
{
    num[0] = 1;
    for(int i=1;i<MAXN;i++)
    {
        num[i] = num[i-1]*i%mod;
        inv[i] = FastPow(num[i],mod-2); //费马
    }

    d[0] = d[1] = 0; //错排
    d[2] = 1;
    for(int i=3;i<=MAXN;i++)
        d[i] = (i-1)*(d[i-1]+d[i-2])%mod;
}

long long C(int n, int m)
{
    if(m == 1) return n;
    if(n == m) return 1;
    return ((num[n]*inv[m])%mod*inv[n-m])%mod;
}

int main(void)
{
    cin >> T;
    find_inv();
    for(int i=1;i<=T;i++)
    {
        scanf("%d%d",&n,&m);
        if(n == m)
            printf("1\n");
        else if(n-m == 1)
            printf("0\n");
        else if(m == 0)
            printf("%lld\n",d[n]);
        else
            printf("%lld\n",(C(n,m)*d[n-m])%mod);
    }
    return 0;
}