幽魂形态(组合数)

题目描述:

题目的大概意思是说有N个人,每个人有B把(不同)锁,从中任意选K个人,一定可以凑齐A把锁,任意比K小的人数,都不能凑齐,求A和B的最小值

输入输出样例

输入N、K,输出最小的A和K (mod 109+7)

solution 

考虑每k-1个人,都无法凑齐锁,所以这k-1个人至少少了一把锁,因为要求A,B最小,可以认为任意k-1个人都没有同一把锁。所以这N个人中可以选出多少个k-1个人,A(锁的总数)就至少有多少。

综上,Amin= $C_n^{k-1}$

靠虑从N个人中选出一个人,在剩下的N-1个人中随便选K-1个人,这个人一定有其他K-1个人没有的一把锁,当枚举所有K-1时,所有的锁恰好枚举一遍(就像是映射)

综上,Bmin=$C_{n-1}^{k-1}$

 

原文地址:https://www.cnblogs.com/Liuz8848/p/10665379.html