Atcoder Beginner Contest 156E(隔板法,组合数学)

seasongirl 2020-02-25

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 7;
const long long mod=1e9+7;
long long fac[N],inv[N];
long long qpow(long long a,long long b){
    long long ans=1;
    while(b){
        if(b&1)
            ans=a*ans%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
void P(){
    fac[0]=1;
    for(int i=1;i<N;i++)
        fac[i]=fac[i-1]*i%mod;
    inv[N-1]=qpow(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%mod;
}
long long C(int a,int b){
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int n,k;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    P();
    cin>>n>>k;
    if(k>=n)//如果k>=n的话,所有1都可以移动,相当于n个相同球放到n个相同盒中,盒子可以空。
        cout<<C(n+n-1,n-1);//n个球和n个盒子总共有2n-1个空隙,把n个盒子插到空隙里,即为C(2n-1,n)=C(2n-1,n-1)
    else{
        long long tot=C(2*n-1,n-1);
        for(int i=1;i<n-k;i++){//n-k个位置至少为1,容斥减去不足n-k个位置至少为1的情况
            tot-=1ll*C(n,i)*C(n-1,i-1)%mod;//n个球放到i个盒子里,每个盒子都不为空
            //先从n个盒子里选出i个盒子,然后n个球之间存在n-1个空隙,把i-1块挡板插到n-1个空隙里,就可以把n个球分为i份且每一份都不为空
            tot+=mod;
            tot%=mod;
        }
        cout<<tot<<‘\n‘;
    }
    return 0;
}