HDU5894【组合数学】

题意：
现在 m个考生人需要坐在有n个座位的圆桌上。
你需要安排位置，使得任意两个考生之间相距至少k个位置。
桌子有编号，考生a和b交换位置视作一种方案，问有多少方案，mod 1e9+7。
(0 < m < n < 1e6, 0 < k < 1000)
看网上的= =、真心菜啊；
思路：
先确定一个人的位置，然后其余人的方案得出，然后有n个位置，最后除以重复的/m;

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int N=1e6+10;
LL f[N];
void init()
{
f[1]=1;
LL i;
for(i=2;i<=1000000;i++)
f[i]=f[i-1]*i%mod;
}
LL cal(LL g,LL x)
{
LL ans=1;
while(g)
{
if(g&1) ans=(ans*x)%mod;
x=(x*x)%mod;
g>>=1;
}
return ans;
}
LL C(LL n,LL m)
{
if(m>n)
return 0;
LL ans=1;
LL i;
//
for(i=1; i<=m; i++) {
//
ans=ans*((n+i-m)*cal(mod-2,i)%mod)%mod;
//
}
ans=f[n]*cal(mod-2,f[m])%mod*cal(mod-2,f[n-m])%mod;
return ans;
}
int main()
{
LL n,m,k;
int t;
init();
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&n,&m,&k);
if(m==1)
{
printf("%lldn",n);
continue;
}
printf("%lldn",n*C(n-1-k*m,m-1)%mod*cal(mod-2,m)%mod);
}
return 0;
}