[ABC156E] Roaming 题解

前言

这哪有蓝，评分似乎有点过了。

思路

既然是要统计每个房间人数的排列，那我们就枚举把所有人都放到 \(i\) 个房间里的方案数，这个用插板法解决，把所有人都放到 \(i\) 个房间里也就是把他们分成 \(i\) 份，这一部分的答案就是在 \(n\) 个人的 \(n-1\) 个空中插入 \(i-1\) 块隔板的方案数，也就是 \(C_{n-1}^{i-1}\)。

我们还要考虑每个非空房间的位置，也就是在 \(n\) 个房间中选出 \(i\) 个房间的方案数，这个很简单，就是 \(C_n^i\)，所以最终答案就是 \(C_n^i \times C_{n-1}^{i-1}\)。

最后记得写线性逆元或者预处理一下阶乘，我因为没写这两玩意挂大分了。

#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
int n,m,ans;
int jc[200005],inv[200005];
int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int C(int x,int y){
    return jc[x]*inv[y]%mod*inv[x-y]%mod;
}
void init(){
    jc[0]=1,inv[0]=1;
    for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
    inv[n]=ksm(jc[n],mod-2);
    for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    init();
    for(int i=1;i<=n;i++){
        if(m>=n-i) ans+=C(n,i)*C(n-1,i-1);
        ans%=mod;
    }
    printf("%lld",ans);
    return 0;
}