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

发布时间：2020-12-13 21:15:35 所属栏目：PHP教程来源：网络整理

导读：题目：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

题目：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,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("%lldn",n);
        else
            printf("%lldn",(C(n-k*m-1,m-1)*n%mod)*qmod(m,mod-2)%mod);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!