排列计数
题目描述
求有多少种长度为 n 的序列 A，满足以下条件：
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多，序列数对 $10^9+7$ 取模。
输入输出格式
输入格式：
第一行一个数 T，表示有 T 组数据。
接下来 T 行，每行两个整数 n、m。
输出格式：
输出 T 行，每行一个数，表示求出的序列数
输入输出样例
输入样例#1：
5
1 0
1 1
5 2
100 50
10000 5000
输出样例#1：
0
1
20
578028887
60695423
说明
测试点 1 ~ 3： $T=1000，n \leq 8，m \leq 8$；
测试点 4 ~ 6： $T=1000，n \leq 12，m \leq 12$；
测试点 7 ~ 9： $T=1000，n \leq 100，m \leq 100$；
测试点 10 ~ 12：$T=1000，n \leq 1000，m \leq 1000$；
测试点 13 ~ 14：$T=500000，n \leq 1000，m \leq 1000$；
测试点 15 ~ 20：$T=500000，n \leq 1000000，m \leq 1000000$
分析：
一道组合数、错排公式的模板。
很显然可以推出公式是$D_{n-m} \times C^m_n$，那么我们只要预处理即可。
错排公式的递推式：$D_n=(n-1) \times (D_{n-1}+D_{n-2})$，组合数的阶乘公式：$C^m_n=\frac{n!}{m! \times (n-m)!}$。
只要预处理$D$数组和数据范围内所有数的阶乘$jc[i]$以及$jc[i]$的逆元$ny[i]$即可。这里求逆元可以直接费马小定理，因为模数是质数。
Code：
//It is made by HolseLee on 14th Sep 2018
//Luogu.org P4071
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; typedef long long ll;
const int N=1e6+;
const ll mod=1e9+;
int T,n,m;
ll jc[N],ny[N],d[N]; template<typename re>
inline void read(re &x)
{
x=; char ch=getchar(); bool flag=false;
while( ch<'' || ch>'' ) {
if( ch=='-' ) flag=true; ch=getchar();
}
while( ch>='' && ch<='' ) {
x=x*+ch-''; ch=getchar();
}
flag ? x=-x : ;
} inline ll power(ll x,ll y)
{
ll ret=;
while( y ) {
if( y& ) ret=(ret*x)%mod;
y>>=, x=(x*x)%mod;
}
return ret;
} void ready()
{
d[]=, d[]=, jc[]=, ny[]=;
for(int i=; i<N; ++i) d[i]=((i-)*(d[i-]+d[i-])+mod)%mod;
for(int i=; i<N; ++i) {
jc[i]=((jc[i-]*i)+mod)%mod;
ny[i]=power(jc[i],mod-);
}
} int main()
{
read(T); ready();
while( T-- ) {
read(n), read(m);
if( m==n ) puts("");
else if( m>n ) puts("");
else if( m== ) printf("%lld\n",d[n]);
else {
printf("%lld\n",((d[n-m]*(ny[m]*ny[n-m]%mod))%mod*jc[n])%mod);
}
}
return ;
}