hdu 5894 组合数学

80 阅读 0 评论 53 点赞

我是靠谱客的博主现实皮皮虾，最近开发中收集的这篇文章主要介绍hdu 5894 组合数学，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目请点击这：

hdu5894

题解参考这篇文章：

https://blog.csdn.net/islittlehappy/article/details/78515249

题意：

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

解法：

首先必须有n>=m+k*m，否则答案是0。

现在先考虑m个人的相对关系(即不考虑座位编号和人对应，先只考虑人与人间的间隔，即位置分配)，
先在n个座位中抽走k*m个，每个人和k个座位绑在一起，一旦这个人有了座位，他后面自动添加这k个座位。
现在因为是确定相对关系，那么第一个人必有一个座位，那么剩下n-1-k*m个座位，在这之中选m-1个作为给其余人座，即C(n-1-k*m,m-1),现在相对位置就形成了。下面开始对号入座。因为说的是至少，所以我们只需空出k*m个位置不坐人，其它位置任挑都是满足条件（至少间隔k个位置）

由于这第一个人有n中选择，选择[1,n]这n个座位编号，所以将答案先乘以n，即n*C(n-1-k*m,m-1)。不过这样做绝对比真实答案要大，因为是个环形，如果第一个人坐到靠后的位置，那么后面的人就会坐到编号较小的位置，所以就算的有重复，因为当初相对位置为第一的人实际不是总是对应最小编号。

想想，已经计算中的所有方法中，相对位置中的每个人实际成为其座位编号最小的人的机会是相等的，故将答案除以m,即n*C(n-1-k*m,m-1)/m。

另：对于m=1，特判，因为1个人没有间隔。

代码参考：标程

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
#define mod 1000000007
LL Jc[1000010];
void init()
{
Jc[0]=Jc[1]=1;
for(LL i=2;i<=1000005;i++)
Jc[i]=Jc[i-1]*i%mod;
}
LL fastpow(LL a,LL n,LL p) ///快速幂 a^n%p
{
LL ans=1;
while(n)
{
if(n&1) ans=ans*a%p;
a=a*a%p;
n>>=1;
}
return ans;
}
LL niyuan(LL a,LL b) ///费马小定理求逆元
{
return fastpow(a,b-2,b);
}
LL C(LL a,LL b)
///计算C(a,b）
{
return Jc[a]*niyuan(Jc[b],mod)%mod*niyuan(Jc[a-b],mod)%mod;
}
LL lucas(LL a,LL b) ///lucas定理求组合数模
{
if(a<mod&&b<mod)
return C(a,b);
else return C(a%mod,b%mod)*lucas(a/mod,b/mod);
}
int main()
{
LL m,n,k;
init();
int ncase;
scanf("%d",&ncase);
while(ncase--) ///求C(x,y)%mod的值
{
scanf("%lld%lld%lld",&n,&m,&k);
if(m==1) {
printf("%dn",n);
}
else if(n>=m+k*m)
printf("%lldn",lucas(n-k*m-1,m-1)*n%mod*fastpow(m,mod-2,mod)%mod);
else {
printf("0n");
}
}
return 0;
}