首页 > 其他 > 详细

#错排,组合计数#洛谷 4071 [SDOI2016]排列计数

时间:2020-02-24 01:31:15      阅读:77      评论:0      收藏:0      [点我收藏+]

题目

多组询问长度为\(n\)的排列中恰好有\(m\)个数对号入座的排列数


分析

首先\(n\)个数中选择\(m\)个数放入那\(m\)个位置显然是\(C(n,m)\)
剩下就是错排\(D(n)=(n-1)(D(n-1)+D(n-2))\),也很好理解
预处理阶乘逆元错排,\(O(1)\)求解


代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int mod=1000000007;
const int N=1000000;
int d[N+1],fac[N+1],inv[N+1];
inline signed iut(){
    rr int ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans;
}
inline void print(int ans){
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
signed main(){
    fac[0]=fac[1]=inv[0]=inv[1]=1,d[0]=1,d[1]=0;
    for (rr int i=2;i<=N;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,d[i]=1ll*(i-1)*(d[i-2]+d[i-1])%mod;
    for (rr int i=2;i<=N;++i) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod;
    for (rr int T=iut(),Cnm;T;--T){
        rr int n=iut(),m=iut();
        Cnm=1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
        print(1ll*Cnm*d[n-m]%mod),putchar(10);
    }
    return 0;
}

#错排,组合计数#洛谷 4071 [SDOI2016]排列计数

原文:https://www.cnblogs.com/Spare-No-Effort/p/12355285.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!