一眼题，答案就是\(C_m^m*d_{n-m}\)
就是从\(n\)个中选取\(m\)个在位，剩下的错排，之后就是乘法原理了
但是我发现我的错排公式竟然一直不会推
这个递推式很简单，就是\(d[1]=0,d[2]=1,d[n]=(n-1)*(d[n-2]+d[n-1)\)
其实是这样推出来的
我们从\(n\)个元素错排开始考虑，我们特殊判断一下第一个位置不能填\(1\)，但是从\(2\)到\(n\)这\(n-1\)个数可以随便选，于是有\(n-1\)种可能
假设第一次放的的元素是\(k\)
之后剩下的就是
\[1\ 2\ 3\ ...k-1\ \ k+1\ \ k+2\ \ k+3...n
\]
\]
我们可以将这些从小到大对应到\(1\)到\(n-1\)，之后剩下的继续错排就好啦
于是就是\(d[n-1]\)
但是我们这个样子本质上是使得\(k\)那个位置不能放\(k+1\)的（因为\(k+1\)在去掉\(k\)之后是第\(k\)小的），于是我们还可以让\(k\)这个位置放\(k+1\)，之后剩下的继续错排，于是就是\(d[n-2]\)
加法原理这两种不同的情况加起来，再利用乘法原理第一位上有\(n-1\)种选择
于是就有\(d[n]=(n-1)*(d[n-2]+d[n-1])\)
发现luogu日报里竟然又讲错排那就在这里收藏一下
这道题的代码
#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define LL long long
#define maxn 1000005
const int mod=1e9+7;
LL fac[maxn],d[maxn];
int T;
LL x,y;
inline LL read()
{
char c=getchar();
LL x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b) return x=1,y=0,a;
LL r=exgcd(b,a%b,y,x);
y-=a/b*x;
return r;
}
inline LL C(LL n,LL m)
{
LL r=exgcd(fac[m]*fac[n-m]%mod,mod,x,y);
x=(x%mod+mod)%mod;
return fac[n]*x%mod;
}
int main()
{
T=read();
fac[0]=1,fac[1]=1;
for(re int i=2;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
d[0]=1,d[1]=0,d[2]=1;
for(re int i=3;i<=1000000;i++) d[i]=(d[i-1]+d[i-2]%mod)*(i-1)%mod;
LL n,m;
while(T--)
{
n=read(),m=read();
printf("%lld",C(n,m)*d[n-m]%mod);
putchar(10);
}
return 0;
}