题目描述

求有多少种长度为 $n$ 的序列 $A$，满足以下条件：

1. $1∼n$ 这 $n$ 个数在序列中各出现了一次。
2. 若第 $i$ 个数 $A[i]$ 的值为 $i$，则称 $i$ 是稳定的，序列恰好有 $m$ 个数是稳定的。
   由于满足条件的序列可能很多，所以请你将序列数对 $10^9+7$ 取模后输出。

样例

样例输入：

5
1 0
1 1
5 2
100 50
10000 5000

样例输出：

0
1
20
578028887
60695423

这显然是一道数学题。

首先，我们先考虑要让哪 $m$ 个数是稳定的。这显然有 $C^{m}_{n}$ 种选法。

选完这 $m$ 个数后，我们直接把这 $m$ 个数删去，并将剩下的位置和数字按 $1∼n-m$ 重新标号。根据题意，我们要让剩下的 $n-m$ 个数每个数都不在属于自己的位置上。也就是 $\forall i\in [1,n-m],A[i]\ne i$。

这是一个经典的问题——错排问题。记 $d[k]$ 表示 $\forall i\in [1,k],A[i]\ne i$ 的方案总数，则有以下递推公式：$d[k]=(k-1)(d[k-1]+d[k-2])$。其中初值 $d[1]=0,d[2]=1$。这个式子的证明将放在代码之后。

综上，根据乘法原理，题目要求的答案为：$C^{m}_{n}\times d[n-m]$。

特别的，如果 $n=m$，则答案应该为 $1$。在实现时，为了降低编程复杂度，可以令 $d[0]=1$。

此外，我们可以在询问前预处理出 $d[i]$ 和阶乘及其逆元。这样可以做到 $O(1)$ 查询。

所以总的时间复杂度为：预处理 $O(1e6\times \log MOD)$，每次查询 $O(1)$。

代码如下：

#include<iostream>
using namespace std;
const int M=1e6+5,Mod=1e9+7;
int T,n,m,ans;
int d[M],jc[M],jc_inv[M];

inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c-'0');
        c=getchar();
    }
    return x*f;
}

int power(int a,int b,int p){
    int res=1;
    for(;b;b>>=1){
        if(b&1){
            res=1ll*res*a%p;
        }
        a=1ll*a*a%p;
    }
    return res;
}

void init(){
    d[0]=1;
    d[1]=0;
    d[2]=1;
    jc[0]=jc_inv[0]=1;
    jc[1]=jc_inv[1]=1;
    jc[2]=2;
    jc_inv[2]=power(2,Mod-2,Mod);
    for(int i=3;i<=1000000;i++){
        d[i]=(1ll*(i-1)*d[i-1]%Mod+1ll*(i-1)*d[i-2]%Mod)%Mod;
        jc[i]=1ll*jc[i-1]*i%Mod;
        jc_inv[i]=power(jc[i],Mod-2,Mod);
    }
}

int C(int n,int m,int p){
    return 1ll*jc[n]*jc_inv[n-m]%Mod*jc_inv[m]%Mod;
}

int main(){
    T=read();
    init();
    while(T--){
        n=read();
        m=read();
        ans=1ll*C(n,m,Mod)*d[n-m]%Mod;
        printf("%d\n",ans);
    }
    return 0;
}

错排问题递推公式的证明：

对于数字 $k$，它不能放在位置 $k$。所以 $k$ 的放法有 $k-1$ 种。

若 $k$ 放在位置 $m$，我们考虑 $m$ 放在哪个位置：

1. 若 $m$ 放在位置 $k$，则等价于在剩下的 $k-2$ 个数中进行错排问题。此时有 $d[k-2]$ 种。
2. 若 $m$ 不放在位置 $k$，则等价于在除了 $k$ 以外的 $k-1$ 个数中进行错排问题。此时有 $d[k-1]$ 种。

根据加法原理和乘法原理，$d[k]=(k-1)(d[k-1]+d[k-2])$。