题面

Description

求有多少种长度为 n 的序列 A，满足以下条件：

1 ~ n 这 n 个数在序列中各出现了一次

若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的

满足条件的序列可能很多，序列数对 10^9+7 取模。

Input

第一行一个数 T，表示有 T 组数据。

接下来 T 行，每行两个整数 n、m。

T=500000，n≤1000000，m≤1000000

Output

输出 T 行，每行一个数，表示求出的序列数

Sample Input

5

1 0

1 1

5 2

100 50

10000 5000

Sample Output

0

1

20

578028887

60695423

解题思路

　　题目大概就是选\(m\)个，其他错位排列。那么答案显然为\(C_n^m*d[n-m]\)，\(d[i]\)表示长度为\(i\)的错位排列方案数，然后刚开始预处理出\(d\)。

代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int MAXN = 1000005;const int MOD = 1e9+7;typedef long long LL;inline int rd(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}    return f?x:-x;}int T,n,m,d[MAXN],fac[MAXN],inv[MAXN];inline int fast_pow(int x,int y){    int ret=1;    for(;y;y>>=1){        if(y&1) ret=(LL)ret*x%MOD;        x=(LL)x*x%MOD;      }    return ret;}inline LL C(int x,int y){    if(y>x) return 0;    return (LL)fac[x]*inv[y]%MOD*inv[x-y]%MOD;  }int main(){    d[1]=0;d[2]=1;fac[0]=1;d[0]=1;    for(int i=3;i<=1000000;i++) d[i]=(LL)(i-1)*(d[i-1]+d[i-2])%MOD;    for(int i=1;i<=1000000;i++) fac[i]=(LL)fac[i-1]*i%MOD;    inv[1000000]=fast_pow(fac[1000000],MOD-2);    for(int i=1000000-1;~i;i--) inv[i]=(LL)inv[i+1]*(i+1)%MOD;    T=rd();    while(T--){        n=rd(),m=rd();        printf("%lld\n",(LL)d[n-m]*C(n,m)%MOD);    }    return 0;   }