一. 容斥原理

??容斥原理在我们的高中数学中由了解过，就是两个集合A，B的并集的元素个数。同样，在大学里的概率论中也会讲解。

1.1 集合AUB

??在概率论中,我们有这样的一个公式：

A U B = A + B - (A∩B)

如图：

在这里插入图片描述
由于A与B有重叠部分，所以A+B后要减去一次重叠的部分（A∩B）。

1.2 集合AUBUC

A U B U C= A + B + C - (A ∩ B) - (A ∩ C) - (B ∩ C) + (A ∩ B ∩ C)

如图：
在这里插入图片描述
很明显，E，F，G三个部分分别重叠了两次，所以我所我们要减(A ∩ B) ，(A ∩ C) ，(B ∩ C)，但也相当于减了三次G部分(A ∩ B ∩ C)，所以我们还要在加一次(A ∩ B ∩ C)。

以此类推。

二. 知识回顾

推荐专栏：
算法零基础100讲》(第14讲)最小公倍数

??由于今日的题解需要用到最小公倍数，所以我们需要回顾一下，最小公倍数的计算方法。通过定理我们可以很明确的知道，a和b的最小公倍数就等于(a * b) / gcd(a，b)。

三. 课后习题

3.1 丑数 III

题目链接：
1201. 丑数 III

思路分析：
??题目要求我们找出第n个丑数，而题目给定丑数的定义为，能够被a，b，c，整除的数。所以我们最容易想到的就是暴力枚举，从1开始枚举，当遇到a，b，c的约数时，便记录下来，直到找到第n位。
代码如下：

int nthUglyNumber(int n, int a, int b, int c){
	int i = 1;
	int Ugly = 0;
	int cnt = 0;
	while (i){
		if (i % a == 0){
			cnt++;
		}
		else if (i % b == 0){
			cnt++;
		}
		else if (i % c == 0){
			cnt++;
		}
		if (cnt == n){
			Ugly = i;
			break;
		}
		i++;
	}
	return Ugly;
}

但题目给定的数据范围为[1，2000000000]，很明显暴力的解法会超时，而这种时候我们就得想到一种时间复杂度更快的方法，所以我们很容易会想到O(logn)的二分法，但是这种解法与该题由上面联系呢？

接下来我们进行进一步的分析。

首先我们需要知道的是一个数 a 的约数中，小于n的约数个数为 [n / a]；
然后我们还需知道，两个数的a，b的公约数中，小于n的公约数个数为 [n / lcm (a, b)] ,其中lcm是最小公倍数。

??现在我们假设ab , ac , bc分别为a和b，a和c，b和c的最小公倍数，abc为a,b,c的最小公倍数，假设他们不大于n丑数有m个，则m = n / a + n / b + n / c - n / ab - n / ac - n / bc + n / abc。
??有了上面的m，我们在结果区间[1，2000000000]上取中间值mid，计算不大于mid的丑数有m个，我们便可以对m与题目所给的n(这里的n是题目给的n)进行比较，如果m < n则说明小于mid的丑数还不够n个，那么我们就需将mid增大，便将区间转化为[mid + 1，2000000000]，在从中找出新的mid，继续进行比较，直到区间重合，此时的区间值就是我们所求的第n个丑数的值。

代码如下：

#define ll long long
//计算表最大公约数
int gcd(int a, int b){
    return !b ? a : gcd(b, a % b);
}
//计算最小公倍数
ll lcm(int a, int b){
    return (ll)a / gcd(a, b) * b;
}

int nthUglyNumber(int n, int a, int b, int c){
    ll ab = lcm(a, b);//a 和 b的最小共倍数
    ll ac = lcm(a, c);//a 和 c 的最小共倍数
    ll bc = lcm(b, c);//b 和 c 的最小公倍数
    ll abc = lcm(lcm(a, b), c);//a, b, c的最小公倍数
    int left = 1, right = 2000000000;
    while(left < right){
        ll mid = left + (right - left) / 2;
        //不大于mid的约数有多少个
        ll m = mid/a+mid/b+mid/c-mid/ab-mid/ac-mid/bc+mid/abc;
        if(m < n){
            left = mid + 1;
        }
        else{
            right = mid;
        }
    }
    return left;
}

在这里插入图片描述

3.2 播放列表的数量

题目链接：
920. 播放列表的数量

分析：
??这是一道动态规划题，题目给了我们三个参数，n首不同的歌，播放列表长度goal，播放过的歌经过k首后才能在次播放。
思路：

首先我们需定义一个数组dp[goal + 1][n + 1]，dp[i][j]代表长度为 i 的播放列表中恰好包含 j 首不同的歌。
当我们要计算dp[ i ][ j ]时，我们是在dp[i - 1][j - 1]的基础上还剩下n - j + 1首歌未播放，所以我们可以从中任取一首。
又因为题目给定了一个k值，当播放一首歌后，在播放k首歌，即可重复播放该首歌，所以我们还需在dp[i - 1][ j ]的基础上再判断（j - k）是否大于0，如果大于0，则dp[i][j] += dp[i - 1][j] * (j - k)。

代码如下：

#define MOD 1000000007

int numMusicPlaylists(int n, int goal, int k){
    long long dp[goal+1][n+1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1; i <= goal; i++){
        for(int j = 1; j <= n; j++){
            dp[i][j] += dp[i - 1][j - 1] * (n - j + 1);
            dp[i][j] += dp[i - 1][j] * fmax(j - k, 0);
            dp[i][j] %= MOD;
        }
    }
    return dp[goal][n];
}