容斥原理
结论
假设现在有 \(n\) 个集合 \(S_i\)，我们希望求得所有 \(S_i\) 的并集的大小，令集合 \(P=\{1,2,3,\dots,n-1,n\}\)，那么就有公式：
\[\begin{aligned} |\bigcup_{i=1}^nS_i| &= \sum_{i}|S_i|-\sum_{i,j}|S_i\cap S_j|+\sum_{i,j,k}|S_i\cap S_j\cap S_k|-\dots \\ &= \sum_{m=1}^n (-1)^{m-1}\sum_{T\subseteq P,|T|=m}|\bigcap_{i\in T}S_i| \end{aligned} \]这个公式就是容斥原理的内容。
我们可以将容斥原理应用到计数问题。就好比你有 \(n\) 个限制，你要保证至少有 \(m\) 个限制被满足，那么你就可以用容斥模板对其进行思考。
举一个简单的例子：
P1595 信封问题（错排问题）
某人写了 \(n\) 封信和 \(n\) 个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。
我们发现要求的答案就是所有的全排列 \(p\) 的数量减去至少有 \(1\) 个 \(p_i=i\) 的方案数，前者为 \(n!\)，后者我们就可以考虑容斥。
我们设计 \(n\) 个集合 \(S_i\)，第 \(i\) 个集合表示钦定 \(p_i\) 必然等于 \(i\) 的排列数。则我们要求的至少有一个 \(p_i=i\) 的方案数就是 \(|\bigcup_{i=1}^nS_i|\)，我们代入容斥原理的公式：
\[|\bigcup_{i=1}^nS_i|=\sum_{m=1}^n (-1)^{m-1}\sum_{T\subseteq P,|T|=m}|\bigcap_{i\in T}S_i| \]这个式子里要处理的交集并不好直接计算。我们发现后面的交集大小之和其实就是在 \(n\) 个集合中任选 \(m\) 个去求交集大小，即在 \(n\) 个数中任意钦定 \(m\) 个数满足 \(p_i=i\) 的方案数，那么它就转换成了 \(C_{n}^m\times (n-m)!\)，后面的阶乘就是剩下 \(n-m\) 个数重排，不需要考虑它们是否满足 \(p_i=i\)。
那么答案就是：
\[n!-\sum_{m=1}^n(-1)^{m-1}C_{n}^m(n-m)! \]例题
[ARC101E] Ribbons on Tree
如果你硬做 DP 的话，你会发现无论怎么搞都不好优化，根据强大的正难则反原则，我们考虑容斥，用所有可能的配对方案减去不合法的方案。
前者先不管，后者我们就可以想办法定义若干个集合 \(S_i\) 然后与我们的容斥原理形成对接。由于题目是要我们让每条边都染色，那么反过来我们就是要求至少有一条边未被染色的方案数。套路地，设 \(S_i\) 表示钦定第 \(i\) 条边一定不被染色的所有方案，那么我们要求的就是所有 \(S_i\) 的并集大小了。
代入容斥的式子后，你会发现重点还是在于求任选 \(m\) 个 \(S_i\) 的交集之和，这也是容斥原理中一向最难的点。显然地，我们要让 \(m\) 条边不被染色，实际上就是在树上删掉这 \(m\) 条边，然后每个连通块中两两配对。
要在一个大小为 \(k\) 的连通块里任意配对，其实就和我们开头说的要求的总方案数很像。我们设这个方案数为 \(f_k\)，那么就可以得到一个转移 \(f_k=f_{k-2}\times (k-1)\)，原理是你先给 \(1\) 号点选配对对象，这有 \(k-1\) 中可能，那么剩下的 \(k-2\) 就自由发挥。但是如果 \(2 ∤ k\)，那方案数就只能为 \(0\) 了。
如果我们设 \(dp_{i,j}\) 表示 \(\text{Subtree}(i)\) 中删掉 \(j\) 条边的方案数，我们发现无法保留“连通块大小”这个概念，而我们求方案又必须要知道每个连通块的确切大小。因此我们要换一个思路。
我们可以跳出容斥中枚举 \(m\) 的死思维。设 \(dp_{i,j}\) 表示在 \(\text{Subtree}(i)\) 中任意删边，\(i\) 所在连通块大小为 \(j\) 时对整个答案的贡献，只要我们在 DP 的过程中算上 \((-1)^m\) 这个系数就可以了。
具体地，我们枚举 \(i\) 的儿子 \(v\)，以及 \(v\) 所在连通块大小 \(j'\)，得到转移：
-
若 \((i,v)\) 这条边不删，则 \(dp_{i,j+j'}←dp_{i,j}\times dp_{v,j'}\)。
-
若 \((i,v)\) 这条边要删，则 \(dp_{i,j}←(-1)\times dp_{i,j}\times dp_{v,j'}\times f(j')\)，这里的 \(-1\) 便是一个系数，因为此时我们多删了一条边，那么根据容斥里每一项的系数，我们现在就要多乘一个 \(-1\) 上去。
那么我们的答案就是 \(\sum_{i=1}^n dp_{1,i}\times f_i\)。由于总方案数就是 \(dp_{1,n}\)，我们就不用额外用 \(f_n\) 加上上式。
[PA2019] Trzy kule
本题不需要使用容斥公式，它只是代表了容斥这样类似的正难则反思想。
我们的目标要让三个条件中至少满足一个，但是这样的话考虑的情况会很复杂，因此我们需要转换思想，求出三个条件都不满足的情况。
根据观察，我们可以发现当第 \(i\) 位对 \(s_1\) 产生了 \(1\) 的贡献，如果 \(s_{2,i}=s_{1,i}\)，则也会对 \(s_2\) 产生 \(1\) 的贡献，\(s_3\) 同理。我们不妨设计四种状态 \(100,101,110,111\)，这四种状态的第一位表示对 \(s_1\) 产生了 \(1\) 贡献，后面两位就分别表示了此时是否对 \(s_2,s_3\) 同样造成贡献。我们记这四种状态的数量为 \(S_{100},S_{101},S_{110},S_{111}\)，由于每一位必然有一种填法对 \(s_1\) 产生贡献，因此有 \(S_{100}+S_{101}+S_{110}+S_{111}=n\)。
为了使三个条件都不满足，我们肯定只会分别在四种状态中选择若干个去对 \(s_1\) 产生贡献，我们记 \(i,j,x,y\) 分别表示在 \(100,101,110,111\) 四种状态中选择了若干个去对 \(s_1\) 造成贡献。
那么就有：
\[\begin{cases} i+j+x+y>r_1 \\ (S_{100}-i)+(S_{101}-j)+x+y>r_2 \\ (S_{100}-i)+j+(S_{110}-x)+y>r_3 \end{cases} \]我们考虑枚举 \(i,x\) 的值，那么此时除了 \(j,y\) 以外的量都是定值，移项得到：
\[\begin{cases} y+j>r_1-i-x \\ y-j>r_2-S_{100}-S_{101}+i-x \\ y+j>r_3-S_{100}-S_{110}+i+x \end{cases} \]算上 \(y+j,y-j\) 本身满足的取值，整理一下就是：
\[\begin{cases} y+j\geq\max(r_1-i-x+1,r_3-S_{100}-S_{110}+i+x+1,0) \\ y-j\geq\max(r_2-S_{100}-S_{101}+i-x+1,-S_{101}) \end{cases} \]我们简记为 \(y+j\geq A,y-j\geq B\)。我们建立一个平面直角坐标系，并给每个整数点 \((p,q)\) 赋权值，如果 \(\begin{cases}y+j=p \\ y-j=q \end{cases}\) 有符合题意的非负整数解，则权值为 \(C_{S_{111}}^y\times C_{S_{101}}^j\)，否则为 \(0\)。那么现在我们要做的就是询问 \((A,B)\) 右上角的权值之和，可以使用前缀和实现。记录完这个和之后，我们就再乘上 \(C_{S_{100}}^i\times C_{S_{110}}^x\)，最后加起来，就可以得到答案了。
Small Permutation Problem (Hard Version)
这是一个另类的容斥题型：就是将排列问题转换为棋盘问题，然后在棋盘上进行容斥。
具体地，想象一个 \(n\times n\) 的棋盘，我们要在棋盘上放 \(n\) 个棋子，需要保证每一列每一行都恰好有一个棋子。在这道题当中，我们就是要满足对于所有的 \(i\in [1,n]\)，若 \(a_i\not= -1\)，则 \((1,1)\to (i,i)\) 这个矩形中恰好有 \(a_i\) 个棋子。
如果没有 \(a_i=-1\) 的情况的话，则存在合法方案数必然有 \(|a_i-a_{i-1}|\leq 2\)，因为从 \((i+1,i+1)\) 转移到 \((i,i)\) 最多只会在第 \(i\) 列和第 \(i\) 行各放一个棋子，就是 \(2\) 个棋子。那么我们从 \(1\) 到 \(n\) 枚举当前的矩形 \((1,1)\to (i,i)\)，维护当前每行每列可以放的棋子数量，设当前每行每列都可以放 \(c\) 个，然后进行一下分讨：
- 若 \(a_{i-1}=a_i\)，则不需要放棋子，对答案无贡献。
- 若 \(a_{i-1}+1=a_i\)，则我们考虑在矩形边缘选位置，第 \(i\) 行可以放 \(c\) 个，第 \(i\) 列也可以放 \(c\) 个，除去 \((i,i)\) 重复的部分，我们就有 \(2c-1\) 种方案。在这里因为我们放了棋子，所以我们需要让 \(c\leftarrow c-1\)。
- 若 \(a_{i-1}+2=a_i\)，则我们显然不能在 \((i,i)\) 处放置棋子，因为这样的话第 \(i\) 行，第 \(i\) 列都不能放棋子了。那么方案数就是 \((c-1)^2\)，令 \(c\leftarrow c-2\)。
每次拓展 \(i\rightarrow i+1\) 时，我们就让 \(c\leftarrow c+1\)。
现在我们考虑有 \(a_i=-1\) 的情况。我们可以把所有 \(a_i\not=-1\) 的下标提出来，然后只考虑这一部分的下标。设这些下标为 \(j_1,j_2,\dots,j_m\)。延用上面的思路，我们每次都需要考虑 \((j_{i-1},j_{i-1})\) 拓展到到 \((j_i,j_i)\) 这个矩形后，可以在哪些地方放棋子，通过画图可以我们放棋子的范围是 \(j_i\times j_i\) 这个矩形删掉 \(j_{i-1}\times j_{i-1}\) 这一部分后得到的 \(L\) 形。
但是我们不好处理这个问题，因此考虑容斥，先在 \(j_i\times j_i\) 的矩形中任意选择 \(a_{j_i}-a_{j_{i-1}}\) 个可以放的位置，然后减去有若干个棋子放在 \(j_{i-1}\times j_{i-1}\) 的方案数。
设 \(p=j_i-a_{j_{i-1}}\)，\(q=j_{i-1}-a_{j_{i-1}}\)，\(t=a_{j_i}-a_{j_{i-1}}\)。则总方案数就是在 \(p\times p\) 的初始没有棋子的棋盘上放 \(t\) 个棋子，即 \(C_p^{t}\times C_p^t\times t!\)，含义为先确定 \(t\) 个棋子的行，再确定 \(t\) 个棋子的列，最后有 \(t!\) 种方案让行列相互对应。
为了方便表示，设 \(f(x,y)=C_{x}^y\times C_x^y\times y!=C_x^y\times \frac{x!}{(x-y)!}\)。
接下来设 \(S_i\) 表示钦定 \(i\) 个棋子放在 \(j_{i-1}\times j_{i-1}\) 矩形中的方案集合，我们需求：
\[\begin{aligned} |\bigcup_{i=1}^tS_i|&=\sum_{m=1}^t (-1)^{m-1}\sum_{T\subseteq \{1,2,\dots,t\},|T|=m}|\bigcap_{i\in T}S_i| \\ &= \sum_{m=1}^t (-1)^{m-1}f(p-m,t-m)f(q,m) \end{aligned} \]用总方案数减去上面的式子就行了。
若要求总的答案是多少的话，我们直接对于每个容斥的结果求积就行了。
二项式反演
结论
二项式反演是容斥拓展形成的数学工具。
我们设 \(f_i\) 表示钦定 \(i\) 个元素满足限制（但实际上满足限制的可能不只有 \(i\) 个）的方案数，\(g_i\) 表示恰好有 \(i\) 个元素满足限制的方案数，则我们可以很容易地得到一个关系式：
\[f_i=\sum_{j=i}^n g_jC_{j}^i \]既然有 \(g\to f\) 的等式转换，我们其实也有一个 \(f\to g\) 的等式转换：
\[g_i=\sum_{j=i}^n(-1)^{j-i}f_j C_{j}^i \]证明：
\[\begin{aligned}g_i&=\sum_{j=i}^n(-1)^{j-i}f_j C_{j}^i \\ &= \sum_{j=i}^n(-1)^{j-i}C_{j}^i\sum_{k=j}^n g_kC_{k}^j \\ &=\sum_{k=i}^n g_k \sum_{j=i}^k (-1)^{j-i}C_j^i C_k^j \\ &=\sum_{k=i}^ng_k\sum_{j=i}^k(-1)^{j-i}C_k^iC_{k-i}^{j-i} \\ &=\sum_{k=i}^n g_kC_k^i\sum_{j=0}^{k-i}(-1)^jC_{k-i}^j \\ &= \sum_{k=i}^n g_k C_k^i[k=i] \\ &= g_i\end{aligned} \]
因此，对于“恰好”形式的问题，我们可以设计两个数组 \(f_i,g_i\) 来表示钦定 \(i\) 个满足限制和恰好 \(i\) 个满足限制，这样通过二项式反演就能得到正确的答案。
相关推论
整理了一下关于二项式反演的推论：
\[f_n=\sum_{i=n}^N g_iC_{i}^n\iff g_n=\sum_{i=n}^N(-1)^{i-n}f_i C_{i}^n \]\[f_n=\sum_{i=0}^n (-1)^ig_iC_n^i\iff g_n=\sum_{i=0}^n (-1)^i f_iC_n^i \]\[f_n=\sum_{i=n}^N (-1)^ig_iC_i^n\iff g_n=\sum_{i=n}^N (-1)^{i-n}f_iC_i^n \]\[f_n=\sum_{i=0}^n g_iC_n^i\iff g_n=\sum_{i=0}^n (-1)^{n-i}f_iC_n^i \]例题
Positions in Permutations
【恰好】在计数题中是一个非常棒的词，它启示我们用二项式反演，转而去思考如何求【钦定】类的问题。即求出 \(f_i\) 这个钦定 \(i\) 个数满足条件的方案数，然后根据公式反推 \(g_i\) 这个恰好有 \(i\) 个数满足条件的方案数。
容易发现一个情景：如果要同时使得 \(i,i+2\) 都是完美数，那么 \(i+1\) 就会成为一个特殊的量，即如果在 \(i\) 的位置填入 \(i+1\) 这个数，那么 \(i+2\) 的位置就不能填 \(i+1\) 这个数，因为不满足排列的性质。
结合 \(n\) 个数有 \(m\) 个满足条件的形式，我们设计一个 DP，状态必然包括 \((i,j)\)，表示在排列的前 \(i\) 个数中有 \(j\) 个完美数。考虑到要避免一个数 \(i+1\) 同时被填入 \(i,i+2\) 这两个位置，我们设计 \(dp_{i,j,0/1,0/1}\)，表示在前 \(i\) 个数中有 \(j\) 个完美数，\(i\) 这个数是（\(1\)）否（\(0\)）被有效填在了当前排列中，\(i+1\) 这个数是（\(1\)）否（\(0\)）被有效填在了当前排列中，此时的方案数。上面的【有效】指的是被填的这个数造成了一个完美数，比如我们在 \(p_2\) 的位置放一个 \(5\)，由于 \(|2-5|\not= 1\)，那 \(5\) 显然不是有效的。
为了方便转移，我们把未钦定是否为完美数的数的阶乘提出来，即 \(dp_{n,i,0/1,0}\times (n-i)!\) 才能全面地表示钦定 \(i\) 个数为完美数的方案数。
转移的话，先考虑让 \(i\) 成为一个完美数。
- 若 \(p_i=i-1\)，则需保证 \(i-1\) 这个数没有被填过。而此时 \(i+1\) 显然没有被填过，\(i\) 填不填不会影响 \(p_i\) 是完美数，因此 \(dp_{i,j,0,0}\leftarrow dp_{i-1,j-1,0,0}\) 且 \(dp_{i,j,1,0}\leftarrow dp_{i-1,j-1,0,1}\)。
- 若 \(p_i=i+1\)，则 \(i,i-1\) 这两个数是否被填不会产生影响，因此 \(dp_{i,j,0,1}\leftarrow dp_{i-1,j-1,0,0}+dp_{i-1,j-1,1,0}\) 且 \(dp_{i,j,1,1}\leftarrow dp_{i-1,j-1,0,1}+dp_{i-1,j-1,1,1}\)。
再考虑 \(i\) 不是完美数，则有：\(dp_{i,j,x,0}\leftarrow dp_{i-1,j,0,x}+dp_{i-1,j,1,x}\)，其中 \(x\in\{0,1\}\)。
设 \(f_i\) 表示钦定 \(i\) 个数为完美数的方案数，\(g_i\) 表示恰好 \(i\) 个数为完美数的方案数，则有 \(f_i=(dp_{n,i,0,0}+dp_{n,i,1,0})\times (n-i)!\)。接着根据反演公式得到：
\[g_m=\sum_{i=m}^n (-1)^{i-m}f_iC_i^m \]预处理组合数和阶乘即可。
已经没有什么好害怕的了
对于差值的【恰好】貌似不太好处理，我们将题意转换一下，设糖果能量大于药片的配对数量为 \(x\)，则需满足 \(x-(n-x)=k\Rightarrow x=\dfrac{n+k}{2}\)，我们要求的就是恰好有 \(x\) 对糖果能量大于药片的方案数。
【恰好】转换为【钦定】。我们设 \(f_i\) 表示钦定有 \(x\) 对满足条件的方案数。考虑 DP，先将糖果和药片按照能量大小排序，设 \(dp_{i,j}\) 表示处理前 \(i\) 个糖果，已经有 \(j\) 对满足条件的方案数，不考虑内部不满足条件的随机组合，即不满足条件的配对是最后才考虑上去的。
-
如果让第 \(i\) 个糖果去配对一个比它大的药片，那么就不会产生贡献，\(dp_{i,j}\leftarrow dp_{i-1,j}\)。
-
如果让第 \(i\) 个糖果去配对一个比它小的药片，那么就会产生贡献。考虑会有多少个比它小的药片，由于原数组已经排序，我们可以求出所有药片中比它小的数量为 \(v\)，由于我们已经将糖果排了序，前面有 \(j-1\) 个糖果已经配到了 \(j-1\) 个更小的药片，那么 \(i\) 就只剩下了 \(v-j+1\) 个可能的配对对象，因此 \(dp_{i,j}\leftarrow dp_{i-1,j-1}\times (v-j+1)\)。
注意到我们的 DP 不考虑内部不满足条件的随机组合，因此上面的第二种转移不需要考虑 \([1,i-1]\) 中除了 \(j-1\) 个糖果以外的会占到 \([1,v]\) 的糖果。那么 \(f_i=dp_{n,i}(n-i)!\)。根据反演公式：
\[g_x=\sum_{i=x}^n (-1)^{i-x}f_iC_i^x \]输出 \(g_x\) 就行了。
Timber
先思考如何判断一个合法的初始局面，我们可以贪心一下，从前往后枚举每一棵树，如果这棵树可以向左倒就向左倒，如果不行就向右倒，这样下去如果存在一个点被多次覆盖，那么这个初始局面就是不合法的。
因此我们可以设计一个 \(dp_{i,j}\) 表示在贪心策略下，当前确定了左边的前 \(i\) 棵树，最后一个被覆盖的位置为 \(j\) 的合法初始局面数量，这里的 \(j\) 也相当于 \(i\) 倒下后形成的区间的右端点。
考虑从 \((i-1,l)\) 转移到 \((i,j)\)，由于 \((i,j)\) 状态中 \(i\) 倒下后的区间必然为 \([j-k,j]\)，为了满足不相交的条件，我们必然有 \(l<j-k\)。接下来讨论第 \(i\) 棵树的位置是在 \(j\) 还是在 \(j-k\)：
-
若第 \(i\) 棵树的位置为 \(j\)，则它是向左倒的，只需要满足 \(l<j-k\) 即可，因此 \(dp_{i,j}\leftarrow \sum _{l=k+1}^{j-k-1}dp_{i-1,l}\)。
-
若第 \(i\) 棵树的位置为 \(j-k\)，则它是向右倒的，根据贪心策略，此时 \(i\) 一定不能向左倒，那么就有 \((j-k)-k\leq l<j-k\)，即 \(l\in [j-2k,j-k)\)，因此 \(dp_{i,j}\leftarrow \sum_{l=j-2k}^{j-k-1}dp_{i-1,l}\)。
考虑转换一下思路，这个 DP 的本质就是在处理前 \(i\) 个互不相交的区间，然后根据贪心策略来计算，如果第 \(i\) 个区间与第 \(i-1\) 个区间之中隔了数量 \(<k\) 的空位，那么第 \(i\) 个区间就可以是左端点向右倒，右端点向左倒两种覆盖方式；否则就只能是右端点向左倒。
因此我们设 \(f_i\) 表示钦定有 \(i\) 个区间只有 \(1\) 种覆盖方式的方案数，\(g_i\) 表示恰好有 \(i\) 个区间的方案数。则最终答案显然为 \(\begin{aligned} \sum_{i=0}^m 2^{m-i}g_i\end{aligned}\)。
根据反演公式，我们只需要求出 \(f_i\) 即可。如何求 \(f_i\)？我们先减去 \(mk\) 表示 \(m\) 个区间除了左端点的其余 \(k\) 个位置，那么我们就能在 \(n-mk\) 个位置中选择 \(m\) 个位置表示 \(m\) 个左端点，那是因为要满足 \(i\) 个区间与前面的距离 \(\geq k\)，因此我们还要额外删掉 \(ik\) 个位置，最后在 \(m\) 个区间中选择 \(i\) 个并在它们的前面各自插入 \(k\) 个位置，这样得到的初始局面就一定是合法的，方案数为 \(C_{n-mk-ik}^m\times C_{m}^i\)。
则总答案为：
\[\begin{aligned} \sum_{i=0}^m 2^{m-i}g_i &= \sum_{i=0}^m 2^{m-i}\sum_{j=i}^m (-1)^{j-i}f_jC_j^i \\ &= \sum_{j=0}^m f_j\sum_{i=0}^j 2^{m-i}(-1)^{j-i}C_j^i \\ &= \sum_{j=0}^mf_j2^{m-j}\sum_{i=0}^j 2^{j-i}\dfrac{(-1)^j}{(-1)^i}C_j^i \\ &= \sum_{j=0}^m f_j2^{m-j}(-1)^j\sum_{i=0}^j2^{j-i}(-1)^iC_j^i \\ &= \sum_{j=0}^mf_j2^{m-j}(-1)^j(-1+2)^j \\ &= \sum_{j=0}^m f_j2^{m-j}(-1)^j \end{aligned} \]其中第四行到第五行的转换是二项式定理。最后的式子我们就可以直接 \(O(m)\) 求了。
莫比乌斯反演
莫比乌斯函数
我们定义一个定义域为正整数的函数 \(\mu(x)\) 满足以下条件：将 \(x\) 分解为 \(\begin{aligned}\prod_{i=1}^n p_i^{c_i}\end{aligned}\)，其中 \(p_i\) 为质数且互不相同，\(c_i\geq 1\)，若 \(x=1\) 则 \(\mu(x)=1\)，若 \(\exist c_i,c_i>1\) 则 \(\mu(x)=0\)，若 \(\forall c_i,c_i=1\) 则 \(\mu(x)=(-1)^n\)。我们称这个函数为莫比乌斯函数。
莫比乌斯函数是一个积性函数。
莫比乌斯函数也满足下面这个性质：
\[\sum_{d\mid n}\mu(d)=\begin{cases}1 & n=1 \\ 0 & n>1\end{cases} \]结论
莫比乌斯反演具有两种不同的形式：
\[f_n=\sum_{d\mid n} g_d\iff g_n=\sum_{d\mid n}\mu(d)f_{\frac{n}{d}} \]\[f_n=\sum_{n\mid d}g(d)\iff g_n=\sum_{n\mid d}\mu(\frac{d}{n})f_d \]例题
YY的GCD
莫比乌斯函数的入门题。
题目要求 \(\gcd(x,y)\) 为质数，那么我们就可以直接枚举这个质数 \(p\)，然后看有多少对 \((x,y)\) 满足 \(\gcd(x,y)=p\)。接着我们就要开始进行一些的推算：
\[\begin{aligned} & \sum_{p\in \text{Prime}}\sum_{p\mid x}\sum_{p\mid y}[\gcd(x,y)=p] \\ =& \sum_{p\in \text{Prime}}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor} [\gcd(x,y)=1] \end{aligned} \]根据莫比乌斯函数的性质： \(\sum_{d\mid n}\mu(d)=[n=1]\)，我们可以换成：
\[\begin{aligned} & \sum_{p\in \text{Prime}}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor} [\gcd(x,y)=1] \\ = &\sum_{p\in \text{Prime}}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor} \sum_{d\mid \gcd(x,y)}\mu(d) \\ = &\sum_{p\in \text{Prime}}\sum_{d}\mu(d)\sum_{d\mid x}\sum_{d\mid y} 1 \\ = &\sum_{p\in \text{Prime}}\sum_{d}\mu(d)\times \lfloor \dfrac{n}{pd}\rfloor\times \lfloor \dfrac{m}{pd}\rfloor \end{aligned} \]考虑枚举 \(pd\) 的值为 \(t\) 以及质数 \(p\),则原式变为：
\[\sum_{t=1}^{\min(n,m)} \lfloor \dfrac{n}{t}\rfloor\times \lfloor \dfrac{m}{t}\rfloor\sum_{p\in \text{Prime}}\mu(\dfrac{t}{p}) \]后面那个求和显然可以预处理，我们枚举每一个质数 \(p\)，然后依次找它的不超过 \(\min(n,m)\) 的倍数去算贡献。
最后，由于存在 \(10^4\) 组输入，我们可以用整除分块去优化上式，把 \(\begin{aligned}\sum_{p\in \text{Prime}}\mu(\dfrac{t}{p})\end{aligned}\) 优化成前缀和的形式就行了。
Winter is here
设值域上界 \(m=10^6\)。
遇事不决推式子：
\[\begin{aligned} & \sum_{d=2}^m\sum_{k=1}^nkd\sum_{T\in \{1,\dots,n\},|T|=k} [\gcd_{x\in T}x=d] \\ = & \sum_{d=2}^m\sum_{k=1}^nkd \sum_{d\mid b_1}\sum_{d\mid b_2}\dots \sum_{d\mid b_k} [\gcd_{i=1}^k \dfrac{b_i}{d}=1] \\ = & \sum_{d=2}^m\sum_{k=1}^nkd \sum_{d\mid b_1}\sum_{d\mid b_2}\dots \sum_{d\mid b_k}\sum_{x\mid \gcd\{\frac{b_1}{d},\dots,\frac{b_k}{d}\}} \mu(x) \\ = & \sum_{d=2}^m\sum_{k=1}^nkd\sum_{x}\mu(x) \sum_{xd\mid b_1}\sum_{xd\mid b_2}\dots \sum_{xd\mid b_k} 1 \\ = & \sum_{d=2}^md\sum_{x}\mu(x)\sum_{k=1}^nk\sum_{xd\mid b_1}\sum_{xd\mid b_2}\dots \sum_{xd\mid b_k} 1 \end{aligned} \]我们设 \(cnt(i)\) 表示 \(\sum_{j=1}^n [i\mid a_j]\)，则原式可转换为：
\[\begin{aligned} \sum_{d=2}^md\sum_{x}\mu(x)\sum_{k=1}^{cnt(xd)} k\times C_{cnt(xd)}^k \end{aligned} \]我们可以对每一个 \(i\) 预处理一个 \(f_i\) 表示 \(\begin{aligned}\sum_{k=1}^{cnt(i)}k\times C_{cnt(i)}^k\end{aligned}\)，则答案为：
\[\begin{aligned} \sum_{d=2}^md\sum_{x}\mu(x)f_{xd} \end{aligned} \]我们发现枚举的 \(d,x\) 要满足 \(xd\leq m\)，因此时间复杂度为 \(O(m\log m)\)，预处理时间复杂度为 \(O(n\sqrt{m})\)。
Relatively Prime Powers
考虑一个性质：若一个数 \(x\) 是不合法的，那么 \(x\) 必然能被表示为 \(a^b(a\geq 1,b\geq 2,a,b\in \mathbb{Z})\) 的形式，且 \(b\) 是 \(x\) 分解后各个质因数的指数的最大公约数的因数，证明的话根据题意来看还是比较显然的。
我们设 \(f_i\) 表示分解后各个质因数的指数最大公约数为 \(i\) 的倍数的 \(x\) 个数，\(g_i\) 则表示最大公约数恰好为 \(i\) 的 \(x\) 个数。则有：
\[f_i=\sum_{i\mid d}g_d\Longrightarrow g_i=\sum_{i\mid d}\mu(\dfrac{d}{i})f_d \]我们要求的答案即为 \(g_1\)。问题转换为求 \(f_i\)。
根据性质，若一个数 \(x\) 的质因数指数的最大公约数为 \(i\) 的倍数，那么一定有 \(\sqrt[i]{x}\in \mathbb{N}\)，由于 \(x\not= 1\)，我们的 \(f_i\) 就可以表示为 \(\lfloor \sqrt[i]{n}\rfloor-1\)。因此最终的答案为：
\[g_1=\sum_{d=1}^{\log_2^n}\mu(d)(\lfloor \sqrt[d]{n}\rfloor-1) \]不过 CF 好像会卡 pow 的精度，我们就先用 pow 来求一次 \(x=\sqrt[i]{n}\)，然后判断当前这个答案的周围两个数 \(x-1,x+1\) 是否满足 \((x-1)^i\leq n,(x+1)^i\leq n\)，调整一下 \(x\) 的值即可。
Min-Max 容斥
结论
有一个全集 \(U=\{a_1,a_2,\dots,a_n\}\)，对于一个集合 \(S\)，有以下两个关于最大值和最小值的等式：
\[\min_{a_i\in S}\{a_i\}=\sum_{T\subseteq S,T\not= \varnothing} (-1)^{|T|+1}\max_{a_i\in T}\{a_i\} \]\[\max_{a_i\in S}\{a_i\}=\sum_{T\subseteq S,T\not= \varnothing} (-1)^{|T|+1}\min_{a_i\in T}\{a_i\} \]对于第一个等式的证明：
不妨设 \(U\) 中的元素互不相同，若 \(U\) 中存在相同元素则以编号为序。接着，我们让 \(U\) 中元素从小到大排序，设排序后第 \(i\) 个数为 \(b_i\)。
对于一个 \(S\) 的子集 \(T\)，令 \(T\) 中的最大值为 \(b_k\)。
- 若 \(k=1\)，则 \(T=\{b_1\}\)，有 \((-1)^{|T|+1}b_1=b_1\)。
- 若 \(k>1\)，则 \(T\in \{b_1,b_2,\dots,b_k\}\)，我们在 \(T\) 中钦定 \(b_k\) 这个值必然存在，剩余的 \(k-1\) 个数可选可不选，因此可能的 \(T\) 的数量有 \(2^{k-1}\) 个。由于 \(k>1\)，则 \(|T|\) 为奇数和偶数的概率相等，两种答案便会因为 \((-1)^{|T|+1}\) 的差异被完全抵消。
综上，第一个等式成立。
对于第二个等式的证明同理。
但是光是这个等式是没有什么大用的。我们还存在另一种结论：这两个等式在期望最大值最小值的情况下同样成立，即：
\[E(\min_{a_i\in S}\{a_i\})=\sum_{T\subseteq S,T\not= \varnothing} (-1)^{|T|+1}E(\max_{a_i\in T}\{a_i\}) \]\[E(\max_{a_i\in S}\{a_i\})=\sum_{T\subseteq S,T\not= \varnothing} (-1)^{|T|+1}E(\min_{a_i\in T}\{a_i\}) \]扩展 Min-Max 容斥
定义 \(\text{Kthmax}(S)\) 为 \(S\) 中的第 \(k\) 大元素，\(\text{Kthmin}(S)\) 为 \(S\) 中的第 \(k\) 大元素，则我们还有：
\[\text{Kthmax}(S)=\sum_{T\subseteq S,T\not= \varnothing} (-1)^{|T|-k}C_{|T|-1}^{k-1}\min_{a_i\in T}\{a_i\} \]\[\text{Kthmin}(S)=\sum_{T\subseteq S,T\not= \varnothing} (-1)^{|T|-k}C_{|T|-1}^{k-1}\max_{a_i\in T}\{a_i\} \]\[E(\text{Kthmax}(S))=\sum_{T\subseteq S,T\not= \varnothing} (-1)^{|T|-k}C_{|T|-1}^{k-1}E(\min_{a_i\in T}\{a_i\}) \]\[E(\text{Kthmin}(S))=\sum_{T\subseteq S,T\not= \varnothing} (-1)^{|T|-k}C_{|T|-1}^{k-1}E(\max_{a_i\in T}\{a_i\}) \]对于第一个等式的证明：
由于 \(k\) 值给定，我们设一个集合 \(T\) 对应的贡献式子的系数为 \(f(|T|)\)，即：
\[\text{Kthmax}(S)=\sum_{T\subseteq S,T\not= \varnothing} f(|T|)\min_{a_i\in T}\{a_i\} \]我们让全集 \(U\) 中元素从大到小排序，设排序后第 \(i\) 个数为 \(b_i\)。设 \(T\) 中最小值为 \(b_t\)，枚举 \(b_1,b_2,\dots,b_{t-1}\) 中被选入 \(T\) 中的数为 \(i\)，则 \(b_t\) 的贡献次数为 \(\begin{aligned}\sum_{i=1}^{t-1}C_{t-1}^i f(i+1)\end{aligned}\)。为了使得最终的答案为 \(\text{Kthmax}(S)\)，我们需要使得：
\[\sum_{i=1}^{t-1}C_{t-1}^i f(i+1)=[t=k]\iff \sum_{i=1}^tC_t^if(i+1)=[t=k-1] \]令 \(g(t)=[t=k-1]\)，则上式构成二项式反演结构，已知 \(f\to g\) 的关系式，则能够得到 \(g\to f\) 的关系式：
\[\begin{aligned} & f(t+1)=\sum_{i=1}^t (-1)^{t-i}g_iC_t^i=(-1)^{t-k+1}C_t^{k-1} \\ \Longrightarrow & f(t)=(-1)^{t-k}C_{t-1}^{k-1}\end{aligned} \]因此原式成立。
其余证明同理。
例题
Card Collector
翻译一下题意：有 \(n\) 张卡片，每包零食中含有这些卡片的概率分别为 \(p_1,p_2,p_3,\dots,p_n\)，每包至多一张卡片，可能没有卡片，问期望要买多少包零食才能拿到所有的 \(n\) 张卡片。
注意这里的 \(p_i\) 针对的是同一包零食，形象地说，我们可以想象一个圆，其中 \(100p_i\%\) 的部分是第 \(i\) 张卡片，剩余的 \(100(1-\sum p_i)\%\) 的部分就是一张卡片都没有。
我们可以分开考虑，设 \(x_i\) 表示抽到第 \(i\) 张卡片的期望次数，那么问题就是求 \(E(\max\{x_1,x_2,\dots,x_n\})\)。接着，我们使用 Min-Max 容斥的公式：
\[E(\max\{x_1,x_2,\dots,x_n\})=\sum_{S\subseteq \{x_1,\dots,x_n\},S\not=\varnothing}(-1)^{|S|+1}E(\min_{x_i\in S}\{x_i\}) \]因此我们的问题最后转换为，对任意一个集合 \(S\) 求 \(\min\{x_i\}\) 的期望。说人话，就是在我们的圆上随机放点，看期望放多少个点才能让 \(S\) 对应的区域中存在点，这个概率显然为 \(\sum_{x_i\in S}x_i\)，那么期望次数就取一个倒数，变成 \(\begin{aligned}\dfrac{1}{\sum_{x_i\in S}x_i}\end{aligned}\)。
最后对每个集合求和即可。
[HAOI2015] 按位或
设 \(x_i\) 表示二进制上第 \(i\) 位变为 \(1\) 的期望次数，则答案为 \(E(\max\{x_1,x_2,\dots,x_n\})\)，根据 Min-Max 容斥公式可以得到：
\[E(\max\{x_1,x_2,\dots,x_n\})=\sum_{S\subseteq \{x_1,\dots,x_n\},S\not= \varnothing} (-1)^{|S|+1}E(\min_{x_i\in S}\{x_i\}) \]那么问题就转换为：对于每个集合 \(S\)，计算期望多少次才能使得 \(S\) 中存在一位变成 \(1\)。再将期望转换为求概率，通过简单容斥得到概率为 \(1-\sum_{S\cap T}p_T\)，但是我们无法通过 \(O(3^n)\) 的枚举子集去计算子集和。
这个时候我们就可以用到 FMT 快速莫比乌斯变换了，FMT 可以快速求出每个集合的子集和。
考虑到小数运算的误差，我们判断大小关系的时候最好加上一个 eps。