hdu5894 hannnnah_j’s Biological Test（组合数学）

hdu5894

题目

现在 m个考生人需要坐在有n个座位的圆桌上。你需要安排位置，使得任意两个考生之间相距至少k个位置。桌子有编号，考生a和b交换位置视作一种方案，问有多少方案，mod 1e9+7。(0 < m < n < 1e6, 0 < k < 1000)

思路

这位博主讲的很好。http://blog.csdn.net/hjt_fathomless/article/details/52588392
相当于就是说我们就把这(m-1)*k的空位子先抽出来，然后选人，最后的最后无非就是把空位再放回去满足要求.

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll qmod(ll x,int n)
{
ll ans=1;
for(; n; n>>=1)
{
if(n&1) ans=ans*x%mod;
x=x*x%mod;
}
return ans;
}
ll C(int n,int m)
{
if(m>n) return 0;
ll ans=1;
for(int i=1; i<=m; i++)
{
ans=ans*((n+i-m)*qmod(i,mod-2)%mod)%mod;
}
return ans;
}
ll m,n;
int k;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%d",&n,&m,&k);
if(m==1)printf("%I64dn",n);
else
printf("%I64dn",n*C(n-m*k-1,m-1)%mod*qmod(m,mod-2)%mod);
}
return 0;
}

最后

以上就是甜甜可乐为你收集整理的hdu5894 hannnnah_j’s Biological Test（组合数学）的全部内容，希望文章能够帮你解决hdu5894 hannnnah_j’s Biological Test（组合数学）所遇到的程序开发问题。

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