Skip to main content

容斥定理 Inclusion–exclusion principle

image-20240602024215443

2928. Distribute Candies Among Children I

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        cnt = 0
        def traceback(remain, i):
            nonlocal cnt
            if i == 3 and remain != 0:
                return
            if i == 3:
                cnt += 1
                return 
            for k in range(limit + 1):
                if (remain - k) > (2 - i) * limit or (remain - k ) < 0:
                    continue
                traceback(remain - k, i + 1)
        traceback(n, 0)
        return cnt

nonlocal

def subtrack():
 nonlocal cnt

Utilizing the inclusion and exclusion principle

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)

Reference​

  1. Stars and bars (combinatorics)
  2. Inclusion–exclusion principle
  3. 容斥原理，灵神2928题解