n个人的队伍，不存在m个相邻女生的组合总数是多少？

来源：蜘蛛抓取(WebSpider) 时间：2022-05-09 04:18 标签： n个人排成一队甲乙相邻

首先，把民族泛化为分类（category）。

共有 k 种分类，每个人必须属于且只属于其中一个分类。

假设：属于每种分类的概率相等。

要计算 m 个人中有 n 种不同分类个体的概率，函数表示为 F(k, m, n)。

想了半天，只想出一个递归的解法。

令第一个人的分类为 A，那么剩下的 m-1 人中有两种情况：

1）其中有分类为A的人，那么这 m-1 人必须刚好集齐（包含A的） n 种分类：

但其中不是所有的组合都符合我们的需要。我们要求：集齐的这 n 种分类中包含分类A。

2）其中没有分类为A的人，那么这 m-1 人必须刚好集齐（不含A的） n-1 种分类：

但其中不是所有的组合都符合我们的需要。我们要求：集齐的这 n-1 种分类中不包含分类A。


这道题是要求 i 和 j 在一定范围内取值， 能够取出多少对 (i, j) 满足C(i, j) % k = 0 ，由于用例的数字很大，无法用排列组合的公式直接计算来求余，因此需要使用到数论的一个定理——Lucas定理。
定理的详细证明可以去百度百科看，这里只针对这个定理的使用，举个栗子：

通过使用这个定理，C(n, m)通过不断地将 n 和 m 进行 /k 和 %k 操作从而分解为若干个C(a, b)相乘求余，其实这个操作和求k进制数是一样的，横着看可以发现142为47的5进制数，344为99的5进制数。

因此本题变为在 n 和 m 为上界的条件下，求有多少组(i, j) (i >= j)满足k进制表示中，i至少有一位是小于j的。

以C(p, q)为例，考虑每一位的取值情况，定义三个函数:

而每一位的取值和前面的位是否取到 n 和 m 的上界有关，若前面已取到上界，则该位只能取不大于n和m对应位的值。假设5进制数为143123，若前三位已取143，则第四位只能取小于等于1的数，形成递推关系，考虑如下4个状态。

我要回帖

更多关于 n个人排成一队甲乙相邻 的文章

 

随机推荐