AtCoder Beginner Contest 156 E - Roaming

题目链接
首先，如果k>=n的话，显然我们可以构造出所有状态，相当于n个相同球放到n个不同盒中，盒子可以空。
即 $C{(}_{2n-1}^{n-1})$C(2n−1n−1​).
k<n的情况即必须要有 $n-k$n−k个盒子非空，我们把所有情况算出来去掉不合法情况即可。
不合法情况：仅有x个盒子非空 $x\in [1,n-k-1]$x∈[1,n−k−1]，相当于n个球放到x个不同的盒子里每个盒子都非空的情况，算一算即可。
如果能给您带来一些帮助的话，那就请您点个赞再走吧QAQ

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
#define fi first
#define se second
#define pb push_back
const LL mod=1e9+7;
LL fac[N],inv[N];
LL km(LL a,LL b){
  LL 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]=km(fac[N-1],mod-2);
  for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
LL 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);
  P();
  cin>>n>>k;
  if(k>=n){
    k=n;
    cout<<C(n+k-1,k-1);
  }else{
    LL tot=C(2*n-1,n-1);
    for(int i=1;i<n-k;i++){//>= n-k 个位置为1
      tot-=1ll*C(n,i)*C(n-i+i-1,i-1)%mod;
      tot+=mod;
      tot%=mod;
    }
    cout<<tot<<'\n';
  }
  return 0;
}