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\n",(cheng[n]%mod*dao[m]%mod*dao[n-m]%mod*d[n-m]%mod)%mod); } return 0; }
