P4071 [SDOI2016]排列计数

P4071

题意:

给出一个序列，然后$A[i]$的位置放i则称这是稳定的,然后剩下的$n-m$种则是不稳定的,

思路:

稳定的那$m$个数就是在$n$个数中选择$m$个数让他稳定，
然后剩下的不稳定的就是$n-m$个数做错排的方案数,

啥是错排:

错排例题

这就是一个错排的板子题，然后我们按照这个板子题来讲错排的原理，

就是$n$封信，装到$n$个信封中，都装错了.

我们先看第一个人，因为第一个人装错的话有$n-1$种情况，就长这样:

然后拿出其中的一种来看，如果第二封信选择了第一个信封那就是后边的$n-2$个数做错排:

如果第二个没有选第一封信，那就相当于对剩下的$n-1$个做错排.

我们就很容易得到一个递推式（设$f[i]$ 为给i个数做错排的方案数）:

\[(n - 1) \ast (f[n - 1] + f[n - 2])\]

边界条件就是$n$为$1$和$2$的时候，当$n$只有$1$的时候只能放到这个信封中，所以方案数为$0$，

当$n$为$2$的时候只有下图这一种可能,所以方案数为$1$.剩下的递推可得.

求组合数的话我们可以用$Lucas$定理来求得.
$Lucas$定理:
\[Lucas(n, m) \% mod = \tbinom{n \% mod}{m \% mod} * Lucas(n, m)\]

因为这个题中$n,m$太大了，我们可以用公式直接求，因为需要$mod$一个数，

然后因为公式为$\frac {n!} {m!(n - m)!}$ 有除法，因为$mod$意义下没有除法运算，

然后我们可以求出$m!(n - m)!$ 的逆元，让$n!$ 乘以$m!(n - m)!$ 的逆元来求$mod$意义下的组合数.

因为$mod$的这个数为质数，我们可以直接利用费马小定理来求逆元.

费马小定理;
\[a^{p - 1} \equiv 1 \ (mod \ p)\]

所以 \[a \ast a^{p -2} \equiv 1 \ (mod \ p)\]
所以在$mod p $的情况下$a$的逆元就是$a ^ {p - 2}$

做的时候我们可以先处理出前$1000000$的错排和阶乘.

code :

#include <bits/stdc++.h>
#define N 1000010
#define M 1010
#define ll long long

using namespace std;
ll mod = 1e9 + 7;
ll t, n, m, f[N], jc[N];

ll read() {
    ll s = 0, f = 0;
    char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

ll q_pow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

ll c(ll a, ll b) {
    return (jc[a] % mod * q_pow(jc[b] * jc[a - b] % mod, mod - 2) % mod) % mod;
}

ll lucas(ll a, ll b) {
    if (!b) return 1;
    else return (lucas(a / mod, b / mod) * c(a % mod, b % mod)) % mod;
}

int main() {
    t = read();
    f[1] = 0, f[2] = 1, jc[1] = 1, jc[2] = 2;
    for (ll i = 3; i <= 1000000; i++)
        f[i] = ((i - 1) * (f[i - 1] + f[i - 2]) % mod) % mod, jc[i] = (jc[i - 1] * i) % mod;
    while (t--) {
        n = read(), m = read();
        if (n == m) puts("1");
        else if (n - m == 1) printf("0\n");
        else if (m == 0) printf("%lld\n",f[n]);
        else {
            ll ans = (f[n - m] % mod * lucas(n, m)) % mod;
            printf("%lld\n", ans);
        }
    }
    return 0;
}