博客

题目：

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


题意：

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

分析：

这题队友过的，补一下~

首先确定第一个人的位置，第一个人可以从n个椅子中任选一个，然后剩余n-1个椅子。因为人的间隔至少k个椅子，所以从这些符合要求的间隔距离的椅子抽出k*m个，然后剩下的m-1个人就可以随便从剩下的椅子人选了。可以想象成每个人和k个座位绑在一起，一旦这个人有了座位，他后面自动添加这k个座位。

那么第一个人从n个座位中选择一个，并且抽走了k*m个，那么剩下n-1-k*m个座位，在这之中选m-1个作为给其余人座，总数为sum=n*C(n-1-k*m,m-1)，因为这里的人是无差别的。比如有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;
}