zcmimi's blog

查看原题

点击跳转

n个位置中选出m个位置后剩余n-m个位置错排

{n\choose m}\cdot D_{n-m}

#include<bits/stdc++.h>
const int N=1000011,P=1000000007;
int D[N],fac[N],ifac[N];
int C(int n,int m){
    return 1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;
}
int lucas(int n,int m){
    if(!m)return 1;
    return 1ll*C(n%P,m%P)*lucas(n/P,m/P)%P;
}
int pw(int x,int b){
    int res=1;
    for(;b;b>>=1,x=1ll*x*x%P)
        if(b&1)res=1ll*res*x%P;
    return res;
}
int main(){
    D[0]=D[1]=0;D[2]=1;
    fac[0]=fac[1]=1;fac[2]=2;
    for(int i=3;i<=1000000;++i)
        fac[i]=1ll*fac[i-1]*i%P,
        D[i]=1ll*(i-1)*(D[i-1]+D[i-2])%P;
    ifac[1000000]=pw(fac[1000000],P-2);
    for(int i=1000000;i;--i)
        ifac[i-1]=1ll*ifac[i]*i%P;
    int T,n,m;
    for(scanf("%d",&T);T--;)
        scanf("%d%d",&n,&m),
        printf("%d\n",n==m?1:1ll*lucas(n,m)*D[n-m]%P);
}
LG 4071 [SDOI2016]排列计数
comment评论
Search
search