2927：给小朋友们分糖果 III（★★）

力扣第 2927 题

题目

你被给定两个正整数 n 和 limit。

返回 在每个孩子得到不超过 limit 个糖果的情况下，将 n 个糖果分发给 3 个孩子的 总方法数。

示例 1:

输入：n = 5, limit = 2
输出：3
解释：有 3 种方式将 5 个糖果分发给 3 个孩子，使得每个孩子得到不超过 2 个糖果：(1, 2, 2), (2, 1, 2) 和 (2, 2, 1)。

示例 2:

输入：n = 3, limit = 3
输出：10
解释：有 10 种方式将 3 个糖果分发给 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 <= 108
• 1 <= limit <= 108

分析

典型的容斥

解答

1
2
3
4
5
6

def f2(x):
    return x*(x-1)//2 if x>1 else 0

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        return f2(n+2)-3*f2(n-limit+1)+3*f2(n-limit*2)-f2(n-limit*3-1)

0 ms