C++11(clang++ 3.9) 解法, 执行用时: 14ms, 内存消耗: 8420K, 提交时间: 2018-11-02 20:42:15

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
ll n,m,k,fac[1000001]={1ll},ans;
void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0) x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}
ll inv(ll a)
{
    ll x,y;
	exgcd(a,mod,x,y);
    return (x+mod)%mod;
}
ll C(ll n,ll m)
{
    if(n<0||m<0||m>n) return 0;
    return fac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;
}
int main()
{
	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=0;i*(k+1)<=m;i++)
	{
        int ff=i&1?-1:1;
        ans=((ans+ff*C(n,i)%mod*C(n+m-1-i*k-i,n-1))%mod+mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 4348K, 提交时间: 2020-05-11 21:36:57

#include<bits/stdc++.h>
using namespace std;
const int maxn=30005;
const int maxnn=6e5+5;
const int mod=1e9+7;
typedef long long ll;
ll f[maxnn];
ll qpow(ll t,ll c){
    ll ans=1;
    while(c){
        if(c&1) ans=ans*t%mod;
        t=t*t%mod;
        c>>=1;
    }
    return ans;
}
ll C(ll a,ll b)
{
    if(a<b||b<0)return 0;
    return f[a]*qpow(f[b],mod-2)%mod*qpow(f[a-b],mod-2)%mod;
}
int main(void)
{
    int n,m,k;
    cin>>n>>m>>k;
    f[0]=f[1]=1;
    for(ll i=2;i<=n+m;i++) f[i]=f[i-1]*i%mod;
    ll ans=C(m+n-1,n-1);
    int nn=(n+m-1)/(k+1);
    for(int i=1;i<=nn;i++){
        ans=(ans-C(n,i)*C(n+m-1-i*(k+1),n-1)%mod+mod)%mod;
    }
    cout<<ans;
}