hdu_5894_hannnnah_j’s Biological Test(打表找规律)

题目链接：hdu_5894_hannnnah_j’s Biological Test

题意：

有n个不同的位置围成一个圈，现在要安排m个人坐，每个人至少的间隔为k，问有多少种安排

题解：

先打表找规律，最后发现答案为n*C(n-m*k-1,n-m*k-m)/m

然后这里求组合要预处理一下，逆元也预处理一下

最后还要特判m为1的情况

#include<cstdio>
typedef long long ll;
const int P=1e9+7;

const int maxn=1e6+3;
long long inv[maxn]={0,1},a[maxn],b[maxn];

ll pow_mod(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)ans = (ans*a) % P;
        b >>= 1, a = (a*a) % P;
    }
    return ans;
}

ll C(ll x,ll y)
{
    return b[x]*a[y]%P*a[x-y]%P;
}

int main(){
    int t;ll n,m,k;
    b[1]=1;
    for(int i=2;i<maxn;i++)b[i]=b[i-1]*i%P;
    for(int i=1;i<maxn;i++)a[i]=pow_mod(b[i],P-2);
    for(int i=2;i<maxn;i++)inv[i]=inv[P%i]*(P-P/i)%P;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&n,&m,&k);
        ll n0=m*(k+1);
        if(m==1)printf("%lld
",n);
        else if(n<n0)printf("0
");
        else printf("%lld
",(((n*C(n-m*k-1,n-m*k-m))%P)*inv[m])%P);
    }
}