（nice!!!）LeetCode 2928. 给小朋友们分糖果 I（枚举、容斥原理）

2928. 给小朋友们分糖果 I

思路：方法一，三层for循环直接暴力枚举，时间复杂度0(n^3)

class Solution {
public:
    int distributeCandies(int n, int limit) {
        int ans=0;
        for(int i=0;i<=n&&i<=limit;i++){
            for(int j=0;j<=n&&j<=limit;j++){
                for(int k=0;k<=n&&k<=limit;k++){
                    if(i+j+k==n) ans++;
                }
            }
        }
        return ans;
    }
};

思路：方法二，容斥原理。本题相当于是将连续的n个球分成三块，那就相当于在这段区间里插入两个木板进行分割，分割为A、B、C块。注意可以为0，也就是模板可以放在最前面和最后面。
1、先求出所有可能的方案数，也就是在n+2个位置里面选出2个位置，即组合数C(n+2,2)
2、再求出所有不可能的方案数，这里需要用到容斥原理
（1）先求出一个位置超过limit的情况，也就是将limit+1先分出去，剩下的n-limit-1个球进行组合C(n-limit-1+2,2)。这里有三块，也就是C(3,1)=3，即3*C(n-limit-1+2,2)。会发现这里面可能含有两块及以上不满足的情况。
（2）接着求出两个位置超过limit的情况，也就是将2 * -
(limit+1)先分出去，剩下的n-2 * (limit+1)个球进行组合C(n-2 * (limit+1)+2,2)。这里有三块，也就是C(3,2)=3，即3 * C(n-limit-1+2,2)。会发现这里面可能含有三块不满足的情况。
（3）最后求出三个位置超过limit的情况，也就是将3 * (limit+1)先分出去，剩下的n-3 * (limit+1)个球进行组合C(n-3 * (limit+1)+2,2)。这里有三块，也就是C(3,3)=1，即1 * C(n-limit-1+2,2)。
3、所有不可能的方案数=3 * C(n-limit-1+2,2)-3 * C(n-limit-1+2,2)+1 * C(n-limit-1+2,2)
4、最后的符合方案数就是=所有可能的方案数-所有不可能的方案数

注意：C(a,2)，这里的a一定要>=2。

class Solution {
public:
    int c2(int u){
        return u>1? u*(u-1)/2:0;
    }
    int distributeCandies(int n, int limit) {
        return c2(n+2)-(3*c2(n-(limit+1)+2)-3*c2(n-2*(limit+1)+2)+c2(n-3*(limit+1)+2));
    }
};