本文共 879 字，大约阅读时间需要 2 分钟。

正题

题目链接:

题目大意

每次询问$n,m$。求有多少个$n$的排列使得$a_i=i$的数量恰好为$m$个。

解题思路

首先$n$个之中选择$m$个$a_i=i$，选择的方案数为$C_n^m$。剩下的错排就好了

错排推导$$d_i=(i-1)(d_{i-1}+d_{i-2})$$

所以答案就是$$C_n^m\ast d_{n-m}$$

预处理即可。

$code$

#include
   
    #include
    
     #include
     
      #define ll long longusing namespace std;const ll N=1e6+10,XJQ=1e9+7;ll T,n,m,d[N],fac[N];ll power(ll x,ll b){
   	ll ans=1;	while(b){
   		if(b&1) ans=ans*x%XJQ;		x=x*x%XJQ;b>>=1;	}	return ans;}ll C(ll n,ll m){
   return fac[n]*power(fac[m]*fac[n-m]%XJQ,XJQ-2)%XJQ;}int main(){
   	scanf("%lld",&T);	d[0]=d[2]=fac[1]=fac[0]=1;fac[2]=2;	for(ll i=3;i<=1000000;i++)		fac[i]=fac[i-1]*i%XJQ,		d[i]=(i-1)*(d[i-1]+d[i-2])%XJQ;	while(T--){
   		scanf("%lld%lld",&n,&m);		printf("%lld\n",C(n,m)*d[n-m]%XJQ);	}}
     
    
   

转载地址：http://auwaf.baihongyu.com/