P4071 [SDOI2016]排列计数 题解

分析：

线性求逆元：https://blog.csdn.net/qq_34564984/article/details/52292502

代码：

#include<cstdio>
using namespace std;
const long long mod=1000000007;
long long ni[1000005],cheng[1000005],dao[1000005],d[1000005];
int main()
{
	d[0]=1;
	d[1]=0;
	d[2]=1;
	for(long long i=3;i<=1000000;i++)
	{
		d[i]=((i-1)*(d[i-1]+d[i-2]))%mod; 
	}//错排递推公式！！！
	ni[1]=1;//1的逆元为1 
	for(long long i=2;i<=1000000;i++)
	{
		ni[i]=(mod-mod/i)*ni[mod%i]%mod;
	}//求出i的逆元(线性求逆元板子
	cheng[0]=1;
	for(long long i=1;i<=1000000;i++)
	{
		cheng[i]=(cheng[i-1]*i)%mod;
	} //求出i的正常阶乘
	dao[0]=1;
	for(long long i=1;i<=1000000;i++)
	{
		dao[i]=(dao[i-1]*ni[i])%mod;
	} 
	long long T;
	scanf("%lld",&T);
	while(T--)
	{
		long long n,m;
		scanf("%lld%lld",&n,&m);
		printf("%lld
",(cheng[n]%mod*dao[m]%mod*dao[n-m]%mod*d[n-m]%mod)%mod);
	}
	return 0;
}