HDU-5894-hannnnah_j’s Biological Test（组合数取模）

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5894

题意：

m个无差别的人坐n个座位的环，要求两人间隔之间空座不小于k，问有多少种坐法。

题解：

第一个人选择一个位子坐好，然后减去必须空出来的n-m*k个位子，那么剩下的人有C(n-m*k-1,m-1)种方法选择座位，则n*C(n-m*k-1,m-1)，m个人无差别则最后除以m；

所以：ans=n*C(n-m*k-1,m-1)/m

CODE：

#include <bits/stdc++.h>
using namespace std;
#define bug cout<<"bug"<<endl;
#define ll long long
const int MAXN = 1e6+7;
const int MOD = 1e9+7;
const int table = 30;
ll f[10+MAXN];
void get_f()
{
f[0]=f[1]=1;
for(int i=2; i<MAXN; ++i)f[i]=1LL*i*f[i-1]%MOD;
}
ll quick_pow(ll x, ll n)
{
ll ans=1;
while(n)
{
if(n&1)ans=ans*x%MOD;
x=x*x%MOD;
n>>=1;
}
return ans;
}
ll get_inv(ll a)
{
if(a==1)return 1;
return 1LL*get_inv(MOD%a)*(MOD-MOD/a)%MOD;
}
ll inv(ll x)
{
return quick_pow(x,MOD-2);
}
ll C(ll n, ll m)
{
return 1LL*f[n]*inv(f[m])%MOD*inv(f[n-m])%MOD;
}
int main()
{
int T;
get_f();
ll n,m,k;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d",&n,&m,&k);
if(m==1){printf("%I64dn",n);continue;}
ll a=m-1;
ll b=n-m*k-1;
if(b>0&&a<=b)
printf("%I64dn",1LL*C(b,a)*n%MOD*inv(m)%MOD);
else printf("0n");
}
return 0;
}

最后

以上就是神勇香菇为你收集整理的HDU-5894-hannnnah_j’s Biological Test（组合数取模）的全部内容，希望文章能够帮你解决HDU-5894-hannnnah_j’s Biological Test（组合数取模）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。