首先我们知道答案是$C(n,m)*Perm(n-m)$
$Perm(x)$表示为$x$的错排方案数
($n$个数里面选$m$个数作为稳定点，其余点均不在自己的位置上)
错排公式:$Perm(x)=(x-1)Perm(x-1)Perm(x-2)$
考场上这个想了很久。。。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=1000005;
const long long Mod=1e9+7;
const long double eps=1e-10;
int T;
long long Pv[N+1],Px[N+1],Cu[N+1],m,n;
long long Qpow(long long A,long long B){
long long base=A,ans=1;
while(B){
if(B&1)ans=ans*base%Mod;
base=base*base%Mod;
B>>=1;
}
return ans;
}
void Prepare(){
long long s=1;
Px[0]=1;
Pv[0]=1;
for(int i=1;i<=N;i++){
s=s*i%Mod;
Pv[i]=s;
Px[i]=Qpow(s,Mod-2);
}
Cu[0]=1;
Cu[1]=0;
Cu[2]=1;
for(long long i=3;i<=N;i++)Cu[i]=(Cu[i-1]+Cu[i-2])%Mod*(i-1)%Mod;
}
long long C(long long a,long long b){
return Pv[a]*Px[b]%Mod*Px[a-b]%Mod;
}
int main(){
freopen("4517.in","r",stdin);
freopen("4517.out","w",stdout);
scanf("%d",&T);
Prepare();
while(T--){
scanf("%lld %lld",&n,&m);
printf("%lld\n",C(n,m)*Cu[n-m]%Mod);
}
return 0;
}
评论 (0)
