本文涉及知识点

组合数学汇总
【组合数学 隔板法 容斥原理】放球问题

LeetCode2929. 给小朋友们分糖果 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⁶
1 <= limit <= 10⁶

容斥原理+放球问题

盒子不同，球相同，盒子可以为空。插板法。
v[0] = f(3,n)，所有方案数。
v[1] = 3f(3,n-limit-1) ，有一个小朋友超限的方案数。一个小朋友limit+1颗糖，其它任意。
v[2] = 3f(3,n-limit2-2)，有两个小朋友超限的方案数。两个小朋友limit+1颗糖，其它任意。
v[3] = f(3,n-limit3-3)，有三个小朋友超限的方案数。三个小朋友limit+1颗糖，其它任意。
注意：如n为负数，则返回0。
v[0]-v[1]v[2]-v[3]便是解。
时间复杂度：O(1)

代码

核心代码

class Solution {
		public:
			long long distributeCandies(int n, int limit) {
				auto F = [&](long long n) {
					if (n < 0) { return 0LL; }
					return (n + 1) * (n + 2) / 2;//n个相同的球给3个不同的人，可以为空
				};
				const long long c = F(n);
				const long long c1 = F(n - limit - 1) * 3;
				const long long c2 = F(n - (limit + 1) * 2) * 3;
				const long long c3 = F(n - (limit + 1) * 3);
				return c - c1 + c2 - c3;
			}
		};

单元测试

	TEST_METHOD(TestMethod11)
		{
			Solution sln;		
			auto res = sln.distributeCandies(5, 2);
			AssertEx(3LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			Solution sln;
			auto res = sln.distributeCandies(3, 3);
			AssertEx(10LL, res);
		}