错排

11450: 错排

时间限制: 1 Sec 内存限制: 128 MB
提交: 75 解决: 41
[提交] [状态] [命题人:admin]

题目描述

求有多少种长度为n的序列A，满足以下条件：
1.1~n这n个数在序列中各出现了一次。
2.若第i个数Ai的值为i，则称i是稳定的。序列恰好有m个数是稳定的。
满足条件的序列可能很多，序列数对10⁹+7取模。

输入

第一行一个数T，表示有T组数据。
接下来T行，每行两个整数n,m。

输出

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

样例输入

样例输出

提示

T=500000,n,m≤10⁶
数据有梯度。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e6+6;
int T,n,m;
ll inv[maxn<<1],fac[maxn<<1],dif[maxn<<1];
ll fast_pow(ll a,ll b){
      ll ans=1;
      while(b){
          if(b&1)ans=(ans%mod*a%mod)%mod;
          a=a*a%mod;
          b>>=1;
      }
      return ans;
}
ll prepare(){
       fac[0]=inv[0]=1;
       for(int i=1;i<=maxn;i++)fac[i]=(fac[i-1]%mod*i)%mod,inv[i]=fast_pow(fac[i],mod-2);
       dif[1]=0,dif[2]=dif[0]=1;
       for(int i=3;i<=maxn;i++)dif[i]=(i-1)*(dif[i-1]+dif[i-2])%mod;
}
int main()
{
    scanf("%d",&T);
    prepare();
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%lld
",fac[n]%mod*inv[m]%mod*inv[n-m]%mod*dif[n-m]%mod);
    }
    return 0;
}