M2929.给小朋友们分糖果 II

combinatorics, https://leetcode.cn/problems/distribute-candies-among-children-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

隔板法（Stars and Bars）是一种直观且强大的数学工具，用于解决相同元素分配到不同组的问题。它的核心思想是通过“插入隔板”来划分元素，从而将组合问题转化为几何或排列问题。

注意：每个位置都可以是星星或隔板。隔板可以相邻。

python

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        def C2(x):
            # C(x + 2, 2)
            return (x + 2) * (x + 1) // 2 if x >= 0 else 0

        total = C2(n)
        over1 = 3 * C2(n - (limit + 1))
        over2 = 3 * C2(n - 2 * (limit + 1))
        over3 = C2(n - 3 * (limit + 1))

        return total - over1 + over2 - over3

我们一步步解释这个公式的来源。先看懂核心目标是什么：

🎯 目标

我们要找出有多少组 (x, y, z) 满足：

x + y + z = n
每个 x, y, z 都满足 0 <= x, y, z <= limit

✅ 第一步：不加限制的所有解

假如不考虑 limit，我们的问题就是找出非负整数解：

x + y + z = n

这个有一个经典的组合数学公式，叫 "球与盒子" 问题（或称“隔板法”）：

✅ 非负整数解的个数：

方案数=C(n+2,2)

✅ 第二步：把不合法的方案“减掉”

我们只要 从总方案数中减去不合法的方案数，就能得到合法方案数了。

🧠 用容斥原理排除不合法方案

我们记住一个事实：

如果某个小朋友拿了超过 limit 的糖果（比如 x > limit），我们就可以把他的值变成 x' = x - (limit + 1)，转化为一个新的问题：

x' + y + z = n - (limit + 1)

也就是说：我们把“x 超了 limit 的情况”都转化为一个新的不等式问题。

🔁 枚举哪些人超了 limit

我们做 容斥原理，分情况计算：

情况	人数	剩余等式
至少 1 人超过 limit	3 种情况（x 或 y 或 z 超过）	每种是 `C(n - limit - 1 + 2, 2)`
至少 2 人超过 limit	3 种情况（x 和 y，x 和 z，y 和 z 超过）	每种是 `C(n - 2*(limit + 1) + 2, 2)`
全部 3 人超过 limit	1 种情况（x、y、z 都超）	`C(n - 3*(limit + 1) + 2, 2)`

容斥原理公式：

合法方案数=T(n)−A+B−C

🎯 总结一下记忆方法

我们从不限制的解数 C(n + 2, 2) 中：

减去 1 人超 limit 的方案：3 * C(n - (limit+1) + 2, 2)
加回 2 人超 limit 的方案：3 * C(n - 2*(limit+1) + 2, 2)
减去 3 人超 limit 的方案（通常是 0）

M2929.给小朋友们分糖果 II ​

M2929.给小朋友们分糖果 II