AcWing - 230. 排列计数 = 组合数学

https://www.acwing.com/problem/content/232/

错位排列：

D[0] = 1;
D[1] = 0;
for(int i = 2; i <= 1000000; i++) {
    if(i & 1) {
        D[i] = ((ll)i * D[i - 1] - 1ll) % MOD;
        if(D[i] < 0)
            D[i] += MOD;
    } else
        D[i] = ((ll)i * D[i - 1] + 1ll) % MOD;
}

错位排列D[i]表示i个数都不在原来的位置上的排列的个数。

用这个搭配一个组合数就可以使用了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
const int MAXN = 1e6;

ll inv[MAXN + 5], fac[MAXN + 5], invfac[MAXN + 5];

void init_C() {
    int n = MAXN;
    inv[1] = 1;
    for(int i = 2; i <= n; i++)
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    fac[0] = 1, invfac[0] = 1;
    for(int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        invfac[i] = invfac[i - 1] * inv[i] % MOD;
    }
}

inline ll C(ll n, ll m) {
    if(n < m)
        return 0;
    return fac[n] * invfac[n - m] % MOD * invfac[m] % MOD;
}

ll D[MAXN + 5];

void init_D() {
    D[0] = 1;
    D[1] = 0;
    for(int i = 2; i <= 1000000; i++) {
        if(i & 1) {
            D[i] = ((ll)i * D[i - 1] - 1ll) % MOD;
            if(D[i] < 0)
                D[i] += MOD;
        } else
            D[i] = ((ll)i * D[i - 1] + 1ll) % MOD;
    }
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    init_C();
    init_D();
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        if(m > n) {
            puts("0");
            continue;
        }
        ll ans = 1;
        ans *= (C(n, m) * D[n - m]) % MOD;
        printf("%lld\n", ans);

    }
}

AcWing - 230. 排列计数 = 组合数学

原文：https://www.cnblogs.com/Inko/p/11449268.html