其实这道题真的不难,题意就是让我们选出$m$个数,然后剩下的$n-m$个数错排的方案数。

就是$C_{n}^m*D_{n-m}$

如何推导$D_n$?

考虑$n$,有$n-1$个位置可以插入,假设插入的位置为$k$,那么$k$又可以选择插入$n$,剩下的数构成一个$D_{n-2}$的错排;也可以不选择插入$n$,那么这$n-1$个数又可以构成$D_{n-1}$的错排(因为$k$不能放到$n$)

因此$D_n=(n-1)(D_{n-1}+D_{n-2})$

观察一下这个式子,$D_2=1,D_0=1$

$\begin{aligned}D_n-n*D_{n-1}&=-[D_{n-1}-(n-1)D_{n-2}]\\&=(-1)^2[D_{n-2}-(n-2)D_{n-3}]\\&=\cdots=(-1)^{n-2}[D_2-2*D_1]=(-1)^n\end{aligned}$

于是$D_n=n*D_{n-1}+(-1)^n $

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e6+5,mod=1e9+7,M=1e6;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
inline int add(int x,int y){x+=y;if(x>=mod)x-=mod;return x;}
inline int del(int x,int y){x-=y;if(x<0)x+=mod;return x;}
inline int mul(int x,int y){x=1ll*x*y%mod;return x;}
inline int fpow(int a,int b){int ans=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ans=mul(ans,a);return ans;}
int D[N],p[N],inv[N];
int main()
{
    p[0]=1;p[1]=1;for(int i=2;i<=M;i++)p[i]=mul(p[i-1],i);
    inv[0]=1;inv[M]=fpow(p[M],mod-2);for(int i=M-1;i;i--)inv[i]=mul(inv[i+1],i+1);
    D[1]=0;D[2]=1;for(int i=3;i<=M;i++)D[i]=((mul(i,D[i-1])+((i&1)?-1:1))%mod+mod)%mod;
    int T,n,m;qr(T);
    while(T--)
    {
        qr(n),qr(m);int ans=1;
        ans=mul(p[n],mul(inv[m],inv[n-m]));
        if(n-m)ans=mul(ans,D[n-m]);qw(ans);puts("");
    }
    return 0;
}