题目大意:m个猴子分n个桃要求苐一个猴子的桃数严格大于其他猴子,问有多少种分法
题目分析:如果不考虑限制条件,m个猴子分n个桃且每个猴子可能分不到桃,则問题转化为部不定方程非负整数解的个数问题设每个猴子得到的桃子为ai,则:
a1+a2+...+am <= n(ai >= 0且ai为整数),用隔板法可以算出答案为C(n + m - 1, m - 1)现在考虑第一只猴子的桃数严格最大的条件,因为至少有k个猴子的桃数大于等于第一个猴子的情况很好算即假设给了第一支猴子x个桃,先C(m-1, k)从剩下的m-1个猴子里选出k个猴子,每个猴子都给x个桃那么还剩n - (k + 1) * x个桃,把这些桃再分给除了第一个猴子的剩下m-1个猴子的方案数还是之前那个公式最後容斥一下,第一只猴子桃数最大的方案=总方案-至少一个猴子比第一个猴子多的方案数+至少二个猴子比第一个猴子多的方案数-...典型容斥,注意判断组合数的边界还有这题组合数很大,可以用费马小定理预处理组合数公式里分母上阶乘的逆元来求组合数