大致题意: 求长度为(n)的排列中恰有(m)个(a_i=i)的方案数。
大致思路
考虑这(m)种位置共有(C_n^m)种选择方式,剩余(n-m)个位置要满足不存在(a_i=i),可以设这种方案数为(f(n-m))。
于是我们考虑(f(x))该如何递推。
假设当前的第一个数选择了剩余(x-1)个数中的某一个(有(x-1)种选择方式),然后就有两种情况:
- 选中的数同时又选择了第一个数,那么剩下的相当于是(f(x-2))。
- 选中的数并没有选择第一个数,那么剩下的相当于是(f(x-1))。
即,(f(x)=(x-1)(f(x-1)+f(x-2)))。
于是这道题就做完了。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000000
#define X 1000000007
#define C(x,y) (1LL*Fac[x]*IFac[y]%X*IFac[(x)-(y)]%X)
using namespace std;
int n,m,f[N+5],Fac[N+5],IFac[N+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int main()
RI i;for(Fac[0]=i=1;i<=N;++i) Fac[i]=1LL*Fac[i-1]*i%X;//预处理阶乘
for(IFac[N]=QP(Fac[N],X-2),i=N-1;~i;--i) IFac[i]=1LL*IFac[i+1]*(i+1)%X;//预处理阶乘逆元
for(f[0]=1,f[1]=0,f[2]=1,i=3;i<=N;++i) f[i]=1LL*(i-1)*(f[i-1]+f[i-2])%X;//递推
RI Tt;scanf("%d",&Tt);W(Tt--) scanf("%d%d",&n,&m),printf("%d
",1LL*C(n,m)*f[n-m]%X);//求解答案
return 0;
}