点击打开链接
挡板法求解 参考博客点击打开链接
#include <bits/stdc++.h> using namespace std; #define ll long long #define M 1000000007 ll quickpow(ll a,ll b) { ll ans; ans=1; while(b>0) { if(b%2==1) { ans=(ans*a)%M; } a=(a*a)%M; b/=2; } return ans; } ll getc(ll n,ll k) { ll ans,sum1,sum2,i,j; sum1=1,sum2=1,i=n,j=1; while(k--) { sum1=(sum1*i)%M; sum2=(sum2*j)%M; i--,j++; } ans=(sum1*quickpow(sum2,M-2))%M; return ans; } int main() { ll ans; int t,n,m,k; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&k); if(m==1) { printf("%d\n",n); continue; } if(n<m+m*k) { printf("0\n"); continue; } ans=(((getc(n-m*k-1,m-1)*n)%M)*(quickpow(m,M-2)%M))%M; printf("%lld\n",ans); } return 0; }
