错排模板题,错排我是看 这篇博客 学会的。
答案是 $C_n^m * d[n-m]$。$d[n]$ 是指长度为 $n$ 的错排总数。
在线求助一下:d[0] 等于多少??....
Talk is cheap.Show me the code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 1000007, mod = 1e9+7;
int T,n,m;
int d[N],fac[N];
int Pow(int x,int y) {
int res = 1, base = x;
while(y) {
if(y&1) res = res*base%mod; base = base*base%mod; y >>= 1;
}
return res;
}
int C(int n,int m) {
return fac[n]*Pow(fac[n-m],mod-2)%mod*Pow(fac[m],mod-2)%mod;
}
signed main()
{
d[0] = 1, d[1] = 0, d[2] = 1;
for(int i=3;i<N;++i)
d[i] = ((i-1) * ((d[i-1] + d[i-2])%mod)) % mod;
fac[0] = 1;
for(int i=1;i<N;++i)
fac[i] = fac[i-1] * i % mod;
T = read();
while(T--) {
n = read(), m = read();
printf("%lld\n",C(n,m)*d[n-m]%mod);
}
return 0;
}