您当前位置：首页 > php开源 > php教程 > hdu 5894 分位置（组合数学，沈阳网络赛）

hdu 5894 分位置（组合数学，沈阳网络赛）

来源：程序员人生发布时间：2016-11-03 08:37:39 阅读次数：2209次

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5894
题意：

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

分析：

这题队友过的，补1下~
首先肯定第1个人的位置，第1个人可以从n个椅子中任选1个，然后剩余n⑴个椅子。由于人的间隔最少k个椅子，所以从这些符合要求的间隔距离的椅子抽出k*m个，然后剩下的m⑴个人就能够随意从剩下的椅子人选了。可以想象成每一个人和k个坐位绑在1起，1旦这个人有了坐位，他后面自动添加这k个坐位。
那末第1个人从n个坐位当选择1个，并且抽走了k*m个，那末剩下n⑴-k*m个坐位，在这当中选m⑴个作为给其余人座，总数为sum=n*C(n⑴-k*m,m⑴)，由于这里的人是无差别的。比如有3个人,假定他们坐的位置是(2,4,7),那末,(4,2,7),(7,2,4)是重复计算的，所有sum/m。

代码：

#include<bits/stdc++.h>
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;
}
int main() {
    // freopen("f.txt","r",stdin);
    int T;
    scanf("%d",&T);
    ll n,m,k;
    while(T--) {
        scanf("%lld%lld%lld",&n,&m,&k);
        if(m==1)printf("%lld\n",n);
        else
            printf("%lld\n",(C(n-k*m-1,m-1)*n%mod)*qmod(m,mod-2)%mod);
    }
    return 0;
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 【Bash百宝箱】shell内建命令之trap

下一篇 Scala之TypeTags and Manifests

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点