给小朋友们分糖果 II

题目

100127. 给小朋友们分糖果 II

---

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

提示：

• 1 <= n <= 10^6
• 1 <= limit <= 10^6

题解

方法一：

思路

总的分配方案$S = \binom {n+2}{2}$。

组合数学中八个球盒模型之一。无区别的n个球放到有区别的3个盒子，盒子可以为空的方案数。

利用隔板法，将两个无区别隔板放到n个无区别的球中拍成一行的组合数，实际上就是n+2个位置寻找两个隔板的放置位置。

利用容斥原理，用总方案数减去不合法的方案数。

分别考虑$A=至少1个人超过limit的方案数，B=至少2个人超过limit的方案数，C=至少3个人超过limit的方案数$。

一个人超过limit的方式是至少有一个人已经有limit+1个糖果。将剩余n-limit-1个糖果分给三个人的方法数为$\binom{n+2-(limit+1)}{2}$，由于三个人都有可能超过limits，所以$A = 3 \times \binom{n+2-(limit+1)}{2}$

同理$B = 3 \times \binom{n+2-2(limit+1)}{2}, C = \binom{n+2-3(limit+1)}{2}$

合法的方案数$S-(A-(B-C)) = S-A+B-C$

代码

using ll = long long;
class Solution {
public:
    ll c2(ll n) {
        return n>1 ? n*(n-1)/2 : 0;
    }
    long long distributeCandies(int n, int lim) {
        return c2(n+2)-3*c2(n+2-(lim+1))+3*c2(n+2-2*(lim+1))-c2(n+2-3*(lim+1));

    }
};