难度: Medium
给你两个正整数 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 <= 1061 <= limit <= 106运行时间: 28 ms
内存: 16.7 MB
# # O(1) 容斥原理
# https://leetcode.cn/problems/distribute-candies-among-children-ii/solutions/2522969/o1-rong-chi-yuan-li-pythonjavacgo-by-end-2woj/
def c2(n: int) -> int:
return n * (n - 1) // 2 if n > 1 else 0
class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)
这个题解使用了容斥原理来计算分配糖果的总方案数。首先定义一个辅助函数 c2(n)，它计算从 n 个不同元素中选择 2 个元素的组合数，即 n * (n - 1) / 2。对于给定的 n 和 limit，我们可以将问题转化为计算总方案数，然后减去不合法的方案数（即某个小朋友得到的糖果数超过 limit）。具体来说，总方案数为从 n + 2 个不同元素中选择 2 个元素的组合数（相当于给每位小朋友分配 0 到 n 颗糖果，再减去两个额外的'边界'元素）。不合法的方案数可以通过容斥原理计算，即减去每位小朋友得到超过 limit 颗糖果的方案数，加上每两位小朋友都得到超过 limit 颗糖果的方案数，再减去所有三位小朋友都得到超过 limit 颗糖果的方案数。
时间复杂度: O(1)
空间复杂度: O(1)
def c2(n: int) -> int:
# 计算从 n 个不同元素中选择 2 个元素的组合数
return n * (n - 1) // 2 if n > 1 else 0
class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
# 使用容斥原理计算分配糖果的总方案数
return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)
在题解中，使用了容斥原理来确保考虑了所有不合法的方案。首先，我们计算每个小朋友得到超过 limit 颗糖果的情况，这是通过 `c2(n - limit + 1)` 计算，代表从 n - limit + 1 个糖果中选择 2 个糖果的组合数，相当于每个小朋友至少得到 limit + 1 颗糖果的情况。然后，通过容斥原理，我们加上了两位小朋友同时得到超过 limit 颗糖果的方案数，再减去三位小朋友都得到超过 limit 颗糖果的方案数，以此类推。这种方法能够确保所有组合的不合法情况被精确地计算和考虑。
函数 c2(n) 在 n <= 1 时返回 0 是基于组合数学的原理，即从 n 个元素中选择 2 个元素的组合数。当 n 小于 2 时，无法选出 2 个元素，因此返回 0 是合理的。对于 n 为负数的情况，根据组合数学的定义，负数个元素中选择两个元素是没有意义的，因此返回 0 依然是合理且正确的处理方法。
在计算总方案数时使用 `c2(n + 2)` 是为了模拟 '边界元素' 的概念。在给小朋友分糖果时，我们可以考虑每个小朋友分到的糖果数为从 0 到 n 之间的任意数。这里的 '+2' 代表两个虚拟的或边界元素，这样做可以帮助我们处理边界情况，确保每位小朋友分到的糖果数在正确的范围内。它实际上是在数轴上添加两个额外点来帮助计算从 0 到 n 颗糖果的分配方式。