洛谷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;
}