题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5894
题意：
一个圆桌上有$n$个不同的位置，$m$个相同的人安排到这$n$个位置上，要求两人相邻的人至少相距$k$个位置，问有多少种安排方法？
分析:
我们可以将$1个人的位置和他旁边的k个位置绑定$看成一个盒子，剩下的$n-m\times (k+1)$个空位置看成若干相同的球，那么这些空位置的插入问题就可以转化为将 $a个相同的球放入b个不同的盒子中$，此时$a=n - m \times (k+1)，b = m-1$。
利用插板法，想象$a$个球排成一排，中间有$a-1$个空位，取$b-1$个板子，插入到这些空中，由于板子不能插入到同一个地方，则此时没有空盒，与题意不符，那么就先给每个盒子放一个球，求出此时的插板方法数，为${a + b-1 \choose {b-1}}$，即${n - m \times k - 1 \choose {m-1}}$。
位置不同，第一个盒子的位置有$n$种，最后要乘上$n$。人是相同的，最后要除以$m$。
注意判断$n-m\times k - 1$是否大0，还一定要先特判$m=1$的情况，此时答案为$n$【在这个地方$wa$了无数次。
$m,n$都不是很大，直接打表预处理一下阶乘直接求组合数即可。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<set> #include<map> #include<algorithm> using namespace std; const int maxn = 1e6 + 5, mod = 1e9 + 7; typedef long long ll; ll fact[maxn]; void init() { fact[0] = 1; for(int i = 1; i < maxn; i++) fact[i] = fact[i - 1] * 1ll * i % mod; } ll quick_pow(ll b, int a) { ll ans = 1; for(; a; a >>= 1, b = b * b % mod){ if(a & 1) ans = ans * b % mod; } return ans; } int main (void) { init(); int T;scanf("%d",&T); while(T--){ ll m, n, k;scanf("%I64d%I64d%I64d", &n, &m, &k); if(m == 1){ printf("%I64d\n", n); continue; } if(n - 1 < m * k){ puts("0"); continue; } ll nn = n - m * k - 1; ll nm = m - 1; ll ans = fact[nn] * quick_pow(fact[nm], mod - 2) % mod * quick_pow(fact[nn - nm], mod - 2) % mod; ans = ans * n % mod * quick_pow(m, mod - 2) % mod; printf("%I64d\n", ans); } return 0; }
|
