「Bzoj 4571」「SDOI2016」排列计数 (错位排列)

BZOJ 4571
题意：求有多少种长度为 $n$ 的序列 $A$，满足以下条件：
$[1, n]$ 这 $n$ 个数在序列中各出现了一次
若第 $i$ 个数 $A_i$ 的值为 $i$，则称 $i$ 是稳定的。序列恰好有 $m$ 个数是稳定的
满足条件的序列可能很多，序列数对 $10^9+7$ 取模。

我们可以$C^m_n$选出$m$个人来稳定，然后其他就是错位排列。
错位排列可以递推出来，设$n$个数的错位排列是$D(n)$，则有
$$
D(n)=(n-1)(D(n-1)+D(n-2))
$$
证明：考虑$n$这个数放到了$k$位置，有$n-1$种情况。
然后考虑$k$这个数放在哪
1、$k$这个数放在$n$位置，那么显然$n,k$全部被排完，变成了$D(n-2)$的局面
2、$k$这个数不放在$n$位置，那么现在先不放$k$，然后现在我们已经少了一个$n$数和$k$位置，那么其实$k$数等价于现在的$n$数，变成了$D(n-1)$的局面

这里还有一个通项式子
$$
D(n) = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} \cdots + (-1)^n \frac{1}{n!} \right)
$$
证明即使用容斥原理。

ps：不要忘了预处理阶乘逆元的方法求组合数。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 1000000 + 5, MO = 1e9 + 7;

    LL T, n, m, D[MAXN], jc[MAXN], jc_inv[MAXN];

    LL ksm(LL a, LL b) {
        LL ans = 1, bs = a;
        while (b) {
            if (b & 1) ans = (ans * bs) % MO;
            bs = (bs * bs) % MO;
            b >>= 1;
        }
        return ans;
    }
    LL C(LL n, LL m) {
        if (m > n) return 0;
        return jc[n] * jc_inv[m] % MO * jc_inv[n - m] % MO;
    }

    void clean() {
    }
    int solve() {

        clean();
        D[0] = D[2] = 1;
        for (LL i = 3; i <= 1000000; ++i) D[i] = (i - 1) * (D[i - 1] + D[i - 2]) % MO;
        jc[0] = 1, jc_inv[0] = 1;
        for (LL i = 1; i <= 1000000; ++i) jc[i] = jc[i - 1] * i % MO, jc_inv[i] = ksm(jc[i], MO - 2);
        cin >> T;
        while (T--) {
            scanf("%lld%lld", &n, &m);
            printf("%lld\n", C(n, m) * D[n - m] % MO);
        }

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}