C++14(g++5.4) 解法, 执行用时: 116ms, 内存消耗: 2788K, 提交时间: 2019-05-17 21:51:32

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long long ll;
const ll MOD=1e8+7;
ll n,m,k;
LL quickPower(LL a, LL b)
{
    LL ans = 1;
    a %= MOD;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % MOD;
        }
        b >>= 1;
        a = a * a % MOD;
    }
    return ans;
}
 
LL c(LL n, LL m)
{
    if (m > n)
    {
        return 0;
    }
    LL ans = 1;
    for (int i = 1; i <= m; i++)
    {
        LL a = (n + i - m) % MOD;
        LL b = i % MOD;
        ans = ans * (a * quickPower(b, MOD - 2) % MOD) % MOD;
    }
    return ans;
}
 
LL lucas(LL n, LL m)
{
    if (m == 0)
    {
        return 1;
    }
    return c(n % MOD, m % MOD) * lucas(n / MOD, m / MOD) % MOD;
}
ll t1[100010];
ll t2[100010];
ll inv[100011];
void Inv()
{
    for(int i=0;i<=100010;i++)
    {
        inv[i]=quickPower(i,MOD-2);
    }
}
void Init()
{
    t1[0]=1;
    for(int i=1;i<=m;i++)
    {
        t1[i]=t1[i-1]*(m-i+1)%MOD*inv[i]%MOD;
    }
    t2[m-1]=1;
    for(int i=m;i<n;i++)
    {
        t2[i]=t2[i-1]*i%MOD*inv[i-m+1]%MOD;
    }
}
int main()
{
    int t;
    Inv();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&n,&m,&k);
        Init();
        int len=min(m,(n-m)/k);
        ll sum=0;
        ll tem;
        for(int i=0;i<=len;i++)
        {
            int l=i&1?-1:1;
            sum=(sum+t1[i]*t2[n-i*k-1]*l)%MOD;
        }
        while(sum<0)
        sum+=MOD;
        printf("%lld\n",sum);
    }
    return 0;
 }

C++(clang++ 11.0.1) 解法, 执行用时: 12ms, 内存消耗: 3548K, 提交时间: 2022-09-17 00:51:44

#pragma G++ optimize("Ofast")
#pragma G++ optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<functional>
#include<queue>
#include<unordered_map>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<bitset>
#include<random>
#include<iomanip>
#include<numeric>

using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
const int INF=1e9;
const ll inf=1e18;

const int mod=1e8+7;
const int N=2e5+5;

ll fac[N],inv[N];
void init(int x=2e5){
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=x;i++)
	{
		fac[i]=fac[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}
	for(int i=2;i<=x;i++)
	{
		(inv[i]*=inv[i-1])%=mod;
	}
}

ll C(int a,int b){
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}

void solve()
{
	int n,m,k; cin>>n>>m>>k;
	ll ans=0;
	for(int i=0;i<=min(m,(n-m)/k);i++)
	{
		(ans+=C(m,i)*C(n-i*k-1,m-1)%mod*(i&1?-1:1))%=mod;
	}	
	cout<<(ans+mod)%mod<<"\n";
}	

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t=1; cin>>t; init();
	while(t--)solve();
	return 0;
}