洛谷P4071 [SDOI2016]排列计数 题解

题目链接：P4071 [SDOI2016]排列计数

题意：

求有多少种 $1$ 到 $n$ 的排列 $a$，满足序列恰好有 $m$ 个位置 $i$，使得 $a_i = i$。

答案对 $10^9 + 7$ 取模。

输入格式：

输入的第一行是一个整数 $T$，代表测试数据的整数。

以下 $T$ 行，每行描述一组测试数据。

对于每组测试数据，每行输入两个整数，依次代表 $n$ 和 $m$。

输出格式：

共输出 $T$ 行，对于每组测试数据，输出一行一个整数代表答案。

数据范围：

$1 \leq T \leq 5 \times 10^5$，$1 \leq n \leq 10^6$，$0 \leq m \leq 10^6$。

答案：

$$\dbinom{n}{m}\times D(n-m)$$

其中 $D(n)$ 为 $n$ 个数的错排公式，有

$$D(1)=0,~D(2)=1 \\[6pt] D(n) = (n-1)\times [D(n-1) + D(n-2)] ,~n>2$$

注意特判 $n<m$ 和 $n=m$ 的情况。

时间复杂度 $\mathcal{O}(N+Q)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6+15))
const int p = 1e9 + 7;

int d[N],fac[N],invf[N];
int qpow(int a, int b)
{
    int ans = 1, base = a % p;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = ans * base % p;
        base = base * base % p;
    }
    return ans;
}
void init()
{
    fac[0] = 1;
    for(int i=1; i<=N-5; i++) fac[i] = fac[i-1] * i % p;
    invf[N-5] = qpow(fac[N-5], p-2);
    for(int i=N-5; i; i--) invf[i-1] = invf[i] * i % p; 
    d[1] = 0; d[2] = 1;
    for(int i=3; i<=N-5; i++) d[i] = (i-1) * ((d[i-1] + d[i-2])%p) % p;
}
int C(int n,int m)
{ return fac[n] * invf[m] % p * invf[n-m] % p; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q,n,m; init();
    for(cin >> Q; Q--; )
    {
        cin >> n >> m;
        if(n < m) cout << "0\n";
        else if(n == m) cout << "1\n";
        else cout << C(n,m) * d[n-m] % p << '\n';
    }
    return 0;
}