「学习总结」容斥原理

📅 Last Updated: 2021-01-24
📊 Word Count: 570
⏱️ Estimated Reading Time: 4 minutes
📄 PDF 📝 Source

容斥原理 用于解决一类，在已知任意 mm 个集合交集大小的情况下，多个集合求并集大小的问题。

容斥原理

定义及证明

设 UU 中元素有 nn 种不同的属性，而第 ii 种属性称为 PiP_i ，拥有属性 PiP_i 的元素构成集合 SiS_i ，那么

∣⋃i=1nSi∣=∑m=1n(−1)m−1∑ai<ai+1∣⋂i=1mSai∣ \left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right| 其中 aa 为任意长度为 mm 且 值域为 [1,n][1, n] 的不重无序数列。

通过定义可知，容斥原理 用于解决一类，在已知任意 mm 个集合交集大小的情况下，多个集合求并集大小的问题。

对于有限制条件的计数问题，可以转化成求集合交并大小问题，进而通过容斥原理解决。

关于容斥原理的证明，其实就是要保证并集中的每一个元素对答案的贡献为 11 。

对于元素 xx，假设它出现在 T1,T2,⋯ ,TmT_1,T_2,\cdots,T_m 的集合中，那么它的出现次数为

Cnt=∣{Ti}∣−∣{Ti∩Tj∣i<j}∣+⋯+(−1)k−1∣{⋂i=1kTai∣ai<ai+1}∣+⋯+(−1)m−1∣{T1∩⋯∩Tm}∣=Cm1−Cm2+⋯+(−1)m−1Cmm=Cm0−∑i=0m(−1)iCmi=1−(1−1)m=1 \begin{split} Cnt=&|\{T_i\}|-|\{T_i\cap T_j|i<j\}|+\cdots+(-1)^{k-1}\left|\left\{\bigcap_{i=1}^{k}T_{a_i}|a_i<a_{i+1}\right\}\right|\\ &+\cdots+(-1)^{m-1}|\{T_1\cap\cdots\cap T_m\}|\\ =&C_m^1-C_m^2+\cdots+(-1)^{m-1}C_m^m\\ =&C_m^0-\sum_{i=0}^m(-1)^iC_m^i\\ =&1-(1-1)^m=1 \end{split}

计数问题的转化

可以考虑把具有相同属性的计数对象放入同一集合。然后根据题目要求，求出同时具有某些属性的技术对象个数（即：属性对应的集合交集）。 ∣⋂i=1nSi∣=∣U∣−∣⋃i=1nSi‾∣ \left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right| 由于容斥原理本身是求集合并集大小，但是可以通过 上式 转化为求集合交集大小问题。

容斥原理栗题（们）

栗题一

详见不定方程非负整数解计数。

对于限制元素数量下界的要求，处理方式都可以采用，直接对总数减去这个元素的下界，计算取值时直接不考虑下界即可。

栗题二

对于一个 11~nn 的排列 PP，若 ∀i,Pi≠i\forall i ,P_i \not = i 则称其为错位排列。给出 nn ，求长度为 nn 的错位排列个数。

考虑全集 ∣U∣=n!|\mathbb{U}|=n! ，元素属性就是 Pi≠iP_i \not = i，答案就是 ∣⋂i=1nSi∣\left|\bigcap_{i=1}^{n}\limits{S_i}\right|。

考虑到： ∣⋂i=1nSi∣=∣U∣−∣⋃i=1nSi‾∣ \left|\bigcap_{i=1}^{n}S_i\right|=|\mathbb{U}|-\left|\bigcup_{i=1}^n\overline{S_i}\right| 易知：Si‾\overline{S_i} 就是所有 Pi=iP_i = i 的排列。

考虑到： ∣⋃i=1nSi‾∣=∑k=1n(−1)k−1∑a1,…,ak∣⋂i=1kSai∣=∑k=1n(−1)k−1(nk)(n−k)! \begin{split} \left|\bigcup_{i=1}^n\overline{S_i}\right|&=\sum_{k=1}^{n}\limits{(-1)^{k-1}\sum_{a_1,\dots ,a_k}\limits{ \left|\bigcap_{i=1}^{k}\limits{S_{a_i}}\right| }}\\ &=\sum_{k=1}^{n}\limits{(-1)^{k-1}\dbinom{n}{k}(n-k)!}\\ \end{split} 综合上式，得出长度为 nn 的错位排列数为：

Dn=n!−∑k=1n(−1)k−1(nk)(n−k)! D_n=n!-\sum_{k=1}^{n}\limits{(-1)^{k-1}\dbinom{n}{k}(n-k)!}

栗题三

A 和 B 喜欢对图（不一定连通）进行染色，而他们的规则是，相邻的结点必须染同一种颜色。

今天 A 和 B 玩游戏，对于 nn 阶 完全图 G=(V,E)G=(V,E) 。他们定义一个估价函数 F(S)F(S) ，其中 S 是边集， S⊆ES\subseteq E .

F(S)F(S) 的值是对图 G′=(V,S)G'=(V,S) 用 mm 种颜色染色的总方案数。

他们的另一个规则是，如果 ∣S∣|S| 是奇数，那么 A 的得分增加 F(S)F(S) ，否则 B 的得分增加 F(S)F(S) . 问 A 和 B 的得分差值。

出题人千辛万苦凑出的式子

考虑形式化的定义答案： Ans=∑S⊆E(−1)∣S∣−1F(S) Ans=\sum_{S\subseteq E}(-1)^{|S|-1}F(S) 设集合 Q(i,j)Q_{(i, j)} 中的元素为所有 (i,j)(i, j) 有边相连的图的染色方案。考虑到相邻的节点（有边相连）必须染成相同的颜色，所以两节点 i,ji, j 有边相连即 节点 i,ji, j 染成相同的颜色。

易知： F(S)=∣⋂e∈SQe∣ F(S)=\left|\bigcap_{e\in S}\limits{Q_e}\right| 带入原式即：（这里用到了容斥原理的逆用） Ans=∑S⊆E(−1)∣S∣−1∣⋂e∈SQe∣=∣⋃e∈EQe∣ \begin{split} Ans&=\sum_{S\subseteq E}(-1)^{|S|-1}\left|\bigcap_{e\in S}\limits{Q_e}\right|\\ &=\left|\bigcup_{e\in E}\limits{Q_e}\right| \end{split} 答案变成：对一张完全图染色，存在任意两个点同色的方案数。

考虑到两两点都异色的染色方案数为 AmnA_m^n。

所以答案为： mn−Amn m^n-A_m^n 其实容斥原理本质上是集合间交集和并集大小之间的转化。

栗题四

求出： ∑i=1n∑j=1ngcd⁡(i,j) \sum_{i=1}^n \sum_{j=1}^n \gcd(i, j) 其中：n≤105n \le 10^5

考虑枚举 gcd ，设函数 f(g)f(g) 为 以 g 为最大公约数的数对个数。 易知： f(g)=⌊ng⌋2−∑i=2i×g≤nf(i×g) f(g) = \lfloor\frac{n}{g}\rfloor^2 - \sum_{i=2}^{i \times g \le n}f(i \times g) 考虑到当 g>n2g > \frac{n}{2} 时，可以直接得到答案。其余的值逆向递推即可。 ### 栗题五 容斥原理推导欧拉函数通项公式

栗题六

询问 1−n1-n 中有多少数字可以表示成 xy,y>1x^y, y > 1 的形式。其中 n≤1018n \le 10^{18}

枚举 xx 的复杂度为 O(n)\mathcal{O}(\sqrt n) 的。考虑枚举 yy ，这样的复杂度仅为 O(log⁡n)\mathcal{O}(\log n)。枚举一个 yy 后，合法的数字有 (yn)\sqrt[y](n) 个。

易知，当 yy 不等于质数积时，贡献为 0。例如 y=4y=4 时，这里的答案一定被 y=2y=2 时算过一次了。

其余的情况，根据容斥原理的套路，可以发现，容斥系数为 −μ(y)-\mu(y) 。 莫比乌斯函数也被称之为数论容斥系数。

栗题七

DAG 计数。给出点数 nn ，输出 nn 个点的带标号 DAG 的数量，对大质数取模。 其中 n≤5×103n\le 5 \times 10^3

考虑到对于一个 DAG 来说，将其入度为 0 的点剖去之后，剩下的图也是一个 DAG 。这样就成功划分了子问题。

朴素做法

设 f(i,j)f(i, j) 表示 ii 个点的 DAG，有 jj 个点的入度为 00，考虑转移：枚举剥去这 jj 个点后会剩下多少个入度为 0 的点。 f(i,j)=(ij)∑k=1i−j(2j−1)k2j(i−j−k)f(i−j,k) f(i, j) = \dbinom{i}{j} \sum_{k=1}^{i-j}\limits{(2^j-1)^k 2^{j(i-j-k)}f(i-j, k)} 后面的式子分别为：

  • (ij)\dbinom{i}{j} ：在 ii 个标号中选出 jj 个充当入度为 00 的点。
  • (2j−1)k(2^j-1)^k：对于这 kk 个入度为 0 的点，他们可以和之前的 jj 个点随意连边（除了不连任何边的情况）。
  • 2j(i−j−k)2^{j(i-j-k)}：对于这 jj 个点，还可以与除这 kk 个点剩下的 i−j−ki-j-k 个点任意连边，一共有 i×(i−j−k)i \times (i-j-k) 条边可以连。 这样的做法是 O(n3)\mathcal{O}(n^3) 的

优化做法

容斥原理的一般化： 对于两个集合函数 f(S),g(S)f(S), g(S)： f(S)=∑T⊆Sg(T)  ⟺  g(S)=∑T⊆S(−1)∣S∣−∣T∣f(T) f(S) = \sum_{T \subseteq S}\limits{g(T)}\ \ \Longleftrightarrow\ \ g(S) = \sum_{T \subseteq S}\limits{(-1)^{|S| - |T|}f(T)}

f(S)=∑T⊇Sg(T)  ⟺  g(S)=∑T⊇S(−1)∣S∣−∣T∣f(T) f(S) = \sum_{T \supseteq S}\limits{g(T)}\ \ \Longleftrightarrow\ \ g(S) = \sum_{T \supseteq S}\limits{(-1)^{|S| - |T|}f(T)} 前面的式子是 FMT 莫比乌斯变换所加速的式子。

设：f(n,S)f(n, S) 为 nn 个点的 DAG 中 SS 中的点度数为 00，类似地，g(n,S)g(n, S) 为 nn 个点的 DAG 中 至少 SS 中的点度数为 00（钦点）。 易知： g(n,S)=2∣S∣(n−∣S∣)g(n,∅) g(n, S) = 2^{|S|(n - |S|)}g(n, \varnothing)

其中 g,fg, f 有如下关系。 g(n,S)=∑T⊇Sf(n,T) g(n, S)=\sum_{T \supseteq S}f(n, T) 根据容斥原理一般公式： f(n,S)=∑T⊇S(−1)∣S∣−∣T∣g(n,T) f(n, S) = \sum_{T \supseteq S}(-1)^{|S| - |T|}g(n, T)

目的是求出 g(n,∅)g(n, \varnothing)： g(n,∅)=∑T≠∅f(n,T)=∑i=1n∑T,∣T∣=if(n,T) \begin{split} g(n, \varnothing) &=\sum_{T \not = \varnothing}f(n, T)\\ &=\sum_{i=1}^{n}\sum_{T, |T|=i}f(n, T) \end{split} 带入 g,fg, f 的关系式： g(n,∅)=∑T≠∅f(n,T)=∑i=1n∑T,∣T∣=if(n,T)=∑i=1n∑T,∣T∣=i∑S⊇T(−1)∣S∣−∣T∣g(n,S)=∑i=1n∑T,∣T∣=i∑S⊇T(−1)∣S∣−∣T∣2∣S∣(n−∣S∣)g(n−∣S∣,∅)=∑i=1n∑T,∣T∣=i∑S⊇T(−1)∣S∣−i2∣S∣(n−∣S∣)g(n−∣S∣,∅)=∑i=1n∑T,∣T∣=i∑k=in(n−ik−i)(−1)k−i2k(n−k)g(n−k,∅)=∑i=1n(ni)∑k=in(n−ik−i)(−1)k−i2k(n−k)g(n−k,∅) =∑k=1n2k(n−k)g(n−k,∅)∑i=1k(ni)(n−ik−i)(−1)k−i=∑k=1n2k(n−k)g(n−k,∅)∑i=1k(nk)(ki)(−1)k−i=∑k=1n2k(n−k)g(n−k,∅)(nk)∑i=1k(ki)(−1)k−i=∑k=1n2k(n−k)g(n−k,∅)(nk)[(∑i=0k(ki)(−1)k−i1i)−(−1)k]=∑k=1n2k(n−k)g(n−k,∅)(nk)[(1−1)k−(−1)k]=∑k=1n2k(n−k)(nk)(−1)k−1g(n−k,∅) \begin{split} g(n, \varnothing) &=\sum_{T \not = \varnothing}f(n, T)\\ &=\sum_{i=1}^{n}\sum_{T, |T|=i}f(n, T)\\ &=\sum_{i=1}^{n}\sum_{T, |T|=i} \sum_{S \supseteq T}(-1)^{|S| - |T|}g(n, S) \\ &=\sum_{i=1}^{n}\sum_{T, |T|=i} \sum_{S \supseteq T}(-1)^{|S| - |T|}2^{|S|(n-|S|)}g(n-|S|, \varnothing) \\ &=\sum_{i=1}^{n}\sum_{T, |T|=i} \sum_{S \supseteq T}(-1)^{|S| - i}2^{|S|(n-|S|)}g(n-|S|, \varnothing) \\ &=\sum_{i=1}^{n}\sum_{T, |T|=i} \sum_{k=i}^{n}\dbinom{n-i}{k-i}(-1)^{k - i}2^{k(n-k)}g(n-k, \varnothing) \\ &=\sum_{i=1}^{n} \dbinom{n}{i} \sum_{k=i}^{n}\dbinom{n-i}{k-i}(-1)^{k - i}2^{k(n-k)}g(n-k, \varnothing) \\\ &=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\sum_{i=1}^{k}\dbinom{n}{i}\dbinom{n-i}{k-i}(-1)^{k-i} \\ &=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\sum_{i=1}^{k}\dbinom{n}{k}\dbinom{k}{i}(-1)^{k-i} \\ &=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\dbinom{n}{k}\sum_{i=1}^{k}\dbinom{k}{i}(-1)^{k-i} \\ &=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\dbinom{n}{k}\left[\left (\sum_{i=0}^{k}\dbinom{k}{i}(-1)^{k-i}1^i \right)- (-1)^k\right] \\ &=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\dbinom{n}{k}\left[\left ( 1-1 \right)^k- (-1)^k\right] \\ &=\sum_{k=1}^{n}2^{k(n-k)}\dbinom{n}{k}(-1)^{k-1} g(n-k, \varnothing)\\ \end{split}

这样的做法是 O(n2)\mathcal{O}(n^2) 的。

扩展容斥原理

Min-max 容斥

max⁡S=∑T⊆S(−1)∣T∣−1min⁡T(1) \operatorname{max} S = \sum_{T \subseteq S} (-1)^{|T| - 1} \operatorname{min} T \qquad{(1)}

min⁡S=∑T⊆S(−1)∣T∣−1max⁡T \operatorname{min} S = \sum_{T \subseteq S} (-1)^{|T| - 1} \operatorname{max} T

「PKUWC2018」随机游走

给定一棵 nn 个结点的树，你从点 xx 出发，每次等概率随机选择一条与所在点相邻的边走过去。

有 QQ 次询问，每次询问给定一个集合 SS，求如果从 xx 出发一直随机游走，直到点集 SS 中所有点都至少经过一次的话，期望游走几步。

特别地，点 xx（即起点）视为一开始就被经过了一次。

答案对 $998244353 $ 取模。

对于 100%100\% 的数据，有 1≤n≤181\leq n\leq 18，1≤Q≤50001\leq Q\leq 5000，1≤k≤n1\leq k\leq n

设 AiA_i 表示到达从 xx 点出发第一次到达点 ii 的期望时间。

易知：答案就是 E(max⁡i∈S(xi))E\left(\max_{i\in S}\limits{(x_i)}\right)。需要注意的是： E(max⁡i∈S(xi))≠max⁡i∈S(E(xi))E\left(\max_{i\in S}\limits{(x_i)}\right) \not = \max_{i \in S}\limits{\left(E(x_i)\right)}， 详见博文

这是非常有用的，因为期望下的 max⁡\max 和 min⁡\min 是很难求的。

假设有 a,ba,b 两个不相关变量，则 E(max⁡(a,b))≠max⁡(E(a),E(b))E(\max(a,b))≠\max(E(a),E(b))。

例子：抛硬币，a=b={0(50%)1(50%)a=b=\begin{cases}0(50\%) \\ 1(50\%)\end{cases} ,则 E(a)=E(b)=12E(a)=E(b)=\dfrac{1}{2}

那么 max⁡(a,b)={max⁡(0,0)(25%)max⁡(0,1)(25%)max⁡(1,0)(25%)max⁡(1,1)(25%)\max(a,b)=\begin{cases}\max(0,0)(25\%)\\ \max(0,1)(25\%)\\ \max(1,0)(25\%)\\ \max(1,1)(25\%)\end{cases} ,则 E(max⁡(a,b))=0.75E(\max(a,b))=0.75

但是 max⁡(E(a),E(b))=0.5\max(E(a),E(b))=0.5所以期望不能大力拆 max⁡\max 或 min⁡\min 。

——引用自 command_block 的博客。

由 (eq.~eq. 1) 可知： E(max⁡i∈Sxi)=∑T⊆S(−1)∣T∣−1E(min⁡i∈Txi) E\left(\max_{i \in S}\limits{x_i}\right)=\sum_{T \subseteq S}(-1)^{|T|-1}E\left(\min_{i \in T}x_i\right)

考虑如何求出 E(min⁡i∈Txi)E\left(\min_{i \in T}\limits{x_i}\right)

相当于从点 xx 出发，首次到达 TT 中的任意一点的期望时间。

设 f(i)f(i) 表示从结点 ii 出发，到达 TT 首次中的点的期望时间。

对于 i∈T,f(i)=0i \in T, f(i)=0

对于 i∉T,f(i)=1degi(∑v(f(v)+1)+f(fai)+1)i \notin T, f(i) = \dfrac{1}{deg_i}\left(\sum_{v}\limits{\left(f(v) + 1\right)} + f(fa_i) + 1\right)

据说是经典套路：

待定系数法，设 f(i)=Ai×f(fai)+Bif(i)=A_i \times f(fa_i) + B_i f(i)=1degi(∑v(f(v)+1)+f(fai)+1)=1degi(∑v(Avf(i)+Bv+1)+f(fai)+1)=1degi−∑Avf(fai)+degi+∑Bvdegi−∑Av \begin{split} f(i) &= \dfrac{1}{deg_i}\left(\sum_{v}\limits{\left(f(v) + 1\right)} + f(fa_i) + 1\right) \\\\ &= \dfrac{1}{deg_i}\left(\sum_{v}\limits{\left(A_vf(i)+B_v + 1\right)} + f(fa_i) + 1\right) \\\\ &= \dfrac{1}{deg_i -\sum{A_v}} f(fa_i)+\dfrac{deg_i+\sum{B_v}}{deg_i-\sum{A_v}} \end{split} 所以：Ai=1degi−∑Av,Bi=degi+∑Bvdegi−∑AvA_i = \dfrac{1}{deg_i -\sum{A_v}}, B_i=\dfrac{deg_i+\sum{B_v}}{deg_i-\sum{A_v}}

特殊的：对于 i∈Ti \in T , Ai=Bi=0A_i = B_i = 0。

这里的 A,BA, B 可以直接通过树上 dp 求出。同时，可以递推出 f(i)f(i) 的值。

设 F(T)=(−1)∣T∣−1f(x)F(T) = (-1)^{|T|-1}f(x) ,答案就是 ∑T⊆SF(T)\sum_{T \subseteq S}\limits{F(T)}

考虑到这东西是子集和变换，使用 FMT (快速莫比乌斯变换) 预处理即可。然后 O(1)O(1) 回答。

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 1dde6df1224a6e1f05b955c9b00668f13bb5cfaa1c29627abcc931faa3961f5f
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「学习总结」容斥原理.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「学习总结」容斥原理.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../d9112b0582.pdf.md', '-o', 'cache/d9112b0582.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawInline (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \ifLuaTeX
    \usepackage{luacolor}
    \usepackage[soul]{lua-ul}
  \else
    \usepackage{soul}
    \ifXeTeX
      % soul's \st doesn't work for CJK:
      \usepackage{xeCJKfntef}
      \renewcommand{\st}[1]{\sout{#1}}
    \fi
  \fi
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「学习总结」容斥原理},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「学习总结」容斥原理}
  \author{Jiayi Su (ShuYuMo)}
  \date{2021-01-24 17:29:33}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  \textbf{容斥原理} 用于解决一类，在已知任意 \(m\)
  个集合交集大小的情况下，多个集合求并集大小的问题。
  
  \section{容斥原理}\label{ux5bb9ux65a5ux539fux7406}
  
  \subsection{定义及证明}\label{ux5b9aux4e49ux53caux8bc1ux660e}
  
  设 \(U\) 中元素有 \(n\) 种不同的属性，而第 \(i\) 种属性称为 \(P_i\)
  ，拥有属性 \(P_i\) 的元素构成集合 \(S_i\) ，那么
  
  \[
  \left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i \frac{n}{2}\)
  时，可以直接得到答案。其余的值逆向递推即可。 \#\#\# 栗题五
  \href{https://oi-wiki.org/math/inclusion-exclusion-principle/\#_14}{容斥原理推导欧拉函数通项公式}
  
  \subsubsection{栗题六}\label{ux6817ux9898ux516d}
  
  询问 \(1-n\) 中有多少数字可以表示成 \(x^y, y > 1\) 的形式。其中
  \(n \le 10^{18}\)
  
  枚举 \(x\) 的复杂度为 \(\mathcal{O}(\sqrt n)\) 的。考虑枚举 \(y\)
  ，这样的复杂度仅为 \(\mathcal{O}(\log n)\)。枚举一个 \(y\)
  后，合法的数字有 \(\sqrt[y](n)\) 个。
  
  易知，当 \(y\) 不等于质数积时，贡献为 0。例如 \(y=4\)
  时，这里的答案一定被 \(y=2\) 时算过一次了。
  
  其余的情况，根据容斥原理的套路，可以发现，容斥系数为 \(-\mu(y)\) 。
  \textbf{莫比乌斯函数}也被称之为\textbf{数论容斥系数}。
  
  \subsubsection{栗题七}\label{ux6817ux9898ux4e03}
  
  DAG 计数。给出点数 \(n\) ，输出 \(n\) 个点的带标号 DAG
  的数量，对大质数取模。 其中 \(n\le 5 \times 10^3\)
  
  考虑到对于一个 DAG 来说，将其入度为 0 的点剖去之后，剩下的图也是一个 DAG
  。这样就成功划分了子问题。
  
  \paragraph{朴素做法}\label{ux6734ux7d20ux505aux6cd5}
  
  设 \(f(i, j)\) 表示 \(i\) 个点的 DAG，有 \(j\) 个点的入度为
  \(0\)，考虑转移：枚举剥去这 \(j\) 个点后会剩下多少个入度为 0 的点。 \[
  f(i, j) = \dbinom{i}{j} \sum_{k=1}^{i-j}\limits{(2^j-1)^k 2^{j(i-j-k)}f(i-j, k)}
  \] 后面的式子分别为：
  
  \begin{itemize}
  \tightlist
  \item
    \(\dbinom{i}{j}\) ：在 \(i\) 个标号中选出 \(j\) 个充当入度为 \(0\)
    的点。
  \item
    \((2^j-1)^k\)：对于这 \(k\) 个入度为 0 的点，他们可以和之前的 \(j\)
    个点随意连边（除了不连任何边的情况）。
  \item
    \(2^{j(i-j-k)}\)：对于这 \(j\) 个点，还可以与除这 \(k\) 个点剩下的
    \(i-j-k\) 个点任意连边，一共有 \(i \times (i-j-k)\) 条边可以连。
    这样的做法是 \(\mathcal{O}(n^3)\) 的
  \end{itemize}
  
  \paragraph{优化做法}\label{ux4f18ux5316ux505aux6cd5}
  
  容斥原理的一般化： 对于两个集合函数 \(f(S), g(S)\)： \[
  f(S) = \sum_{T \subseteq S}\limits{g(T)}\ \ \Longleftrightarrow\ \ g(S) = \sum_{T \subseteq S}\limits{(-1)^{|S| - |T|}f(T)}
  \]
  
  \[
  f(S) = \sum_{T \supseteq S}\limits{g(T)}\ \ \Longleftrightarrow\ \ g(S) = \sum_{T \supseteq S}\limits{(-1)^{|S| - |T|}f(T)}
  \] 前面的式子是 \texttt{FMT} 莫比乌斯变换所加速的式子。
  
  设：\(f(n, S)\) 为 \(n\) 个点的 DAG 中 \(S\) 中的点度数为
  \(0\)，类似地，\(g(n, S)\) 为 \(n\) 个点的 DAG 中 至少 \(S\)
  中的点度数为 \(0\)（钦点）。 易知： \[
  g(n, S) = 2^{|S|(n - |S|)}g(n, \varnothing)
  \]
  
  其中 \(g, f\) 有如下关系。 \[
  g(n, S)=\sum_{T \supseteq S}f(n, T)
  \] 根据容斥原理一般公式： \[
  f(n, S) = \sum_{T \supseteq S}(-1)^{|S| - |T|}g(n, T)
  \]
  
  目的是求出 \(g(n, \varnothing)\)： \[
  \begin{split}
  g(n, \varnothing) &=\sum_{T \not = \varnothing}f(n, T)\\
  &=\sum_{i=1}^{n}\sum_{T, |T|=i}f(n, T)
  \end{split}
  \] 带入 \(g, f\) 的关系式： \[
  \begin{split}
  g(n, \varnothing) &=\sum_{T \not = \varnothing}f(n, T)\\
  &=\sum_{i=1}^{n}\sum_{T, |T|=i}f(n, T)\\
  &=\sum_{i=1}^{n}\sum_{T, |T|=i}  \sum_{S \supseteq T}(-1)^{|S| - |T|}g(n, S)   \\
  &=\sum_{i=1}^{n}\sum_{T, |T|=i}  \sum_{S \supseteq T}(-1)^{|S| - |T|}2^{|S|(n-|S|)}g(n-|S|, \varnothing)   \\
  &=\sum_{i=1}^{n}\sum_{T, |T|=i}  \sum_{S \supseteq T}(-1)^{|S| - i}2^{|S|(n-|S|)}g(n-|S|, \varnothing)   \\
  &=\sum_{i=1}^{n}\sum_{T, |T|=i}  \sum_{k=i}^{n}\dbinom{n-i}{k-i}(-1)^{k - i}2^{k(n-k)}g(n-k, \varnothing)   \\
  &=\sum_{i=1}^{n} \dbinom{n}{i}  \sum_{k=i}^{n}\dbinom{n-i}{k-i}(-1)^{k - i}2^{k(n-k)}g(n-k, \varnothing)   \\\
  &=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\sum_{i=1}^{k}\dbinom{n}{i}\dbinom{n-i}{k-i}(-1)^{k-i} \\
  &=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\sum_{i=1}^{k}\dbinom{n}{k}\dbinom{k}{i}(-1)^{k-i} \\
  &=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\dbinom{n}{k}\sum_{i=1}^{k}\dbinom{k}{i}(-1)^{k-i} \\
  &=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\dbinom{n}{k}\left[\left (\sum_{i=0}^{k}\dbinom{k}{i}(-1)^{k-i}1^i \right)- (-1)^k\right] \\
  &=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\dbinom{n}{k}\left[\left ( 1-1 \right)^k- (-1)^k\right] \\
  &=\sum_{k=1}^{n}2^{k(n-k)}\dbinom{n}{k}(-1)^{k-1} g(n-k, \varnothing)\\
  \end{split}
  \]
  
  这样的做法是 \(\mathcal{O}(n^2)\) 的。
  
  \subsection{扩展容斥原理}\label{ux6269ux5c55ux5bb9ux65a5ux539fux7406}
  
  \subsection{Min-max 容斥}\label{min-max-ux5bb9ux65a5}
  
  \[
  \operatorname{max} S = \sum_{T \subseteq S} (-1)^{|T| - 1} \operatorname{min} T
  \] \{\#eq:max\_min\}
  
  \[
  \operatorname{min} S = \sum_{T \subseteq S} (-1)^{|T| - 1} \operatorname{max} T
  \]
  
  \subsubsection{「PKUWC2018」随机游走}\label{pkuwc2018ux968fux673aux6e38ux8d70}
  
  给定一棵 \(n\) 个结点的树，你从点 \(x\)
  出发，每次等概率随机选择一条与所在点相邻的边走过去。
  
  有 \(Q\) 次询问，每次询问给定一个集合 \(S\)，求如果从 \(x\)
  出发一直随机游走，直到点集 \(S\)
  中所有点都至少经过一次的话，期望游走几步。
  
  特别地，点 \(x\)（即起点）视为一开始就被经过了一次。
  
  答案对 \$998244353 \$ 取模。
  
  对于 \(100\%\) 的数据，有
  \(1\leq n\leq 18\)，\(1\leq Q\leq 5000\)，\(1\leq k\leq n\)
  
  设 \(A_i\) 表示到达从 \(x\) 点出发第一次到达点 \(i\) 的期望时间。
  
  易知：答案就是
  \(E\left(\max_{i\in S}\limits{(x_i)}\right)\)。需要注意的是：
  \(E\left(\max_{i\in S}\limits{(x_i)}\right) \not = \max_{i \in S}\limits{\left(E(x_i)\right)}\)，
  详见\href{https://www.luogu.com.cn/blog/command-block/min-max-rong-chi-xiao-ji}{博文}
  
  \begin{quote}
  这是非常有用的，因为期望下的 \(\max\) 和 \(\min\) 是很难求的。
  
  假设有 \(a,b\) 两个不相关变量，则 \(E(\max(a,b))≠\max(E(a),E(b))\)。
  
  例子：抛硬币，\(a=b=\begin{cases}0(50\%) \\ 1(50\%)\end{cases}\) ,则
  \(E(a)=E(b)=\dfrac{1}{2}\)
  
  那么
  \(\max(a,b)=\begin{cases}\max(0,0)(25\%)\\ \max(0,1)(25\%)\\ \max(1,0)(25\%)\\ \max(1,1)(25\%)\end{cases}\)
  ,则 \(E(\max(a,b))=0.75\)
  
  但是 \(\max(E(a),E(b))=0.5\)所以期望不能大力拆 \(\max\) 或 \(\min\) 。
  
  ——引用自 command\_block 的博客。
  \end{quote}
  
  由 (eq.\textasciitilde{}@eq:max\_min) 可知： \[
  E\left(\max_{i \in S}\limits{x_i}\right)=\sum_{T \subseteq S}(-1)^{|T|-1}E\left(\min_{i \in T}x_i\right)
  \]
  
  考虑如何求出 \(E\left(\min_{i \in T}\limits{x_i}\right)\)
  
  相当于从点 \(x\) 出发，首次到达 \(T\) 中的任意一点的期望时间。
  
  设 \(f(i)\) 表示从结点 \(i\) 出发，到达 \(T\) 首次中的点的期望时间。
  
  对于 \(i \in T, f(i)=0\)
  
  对于
  \(i \notin T, f(i) = \dfrac{1}{deg_i}\left(\sum_{v}\limits{\left(f(v) + 1\right)} + f(fa_i) + 1\right)\)
  
  \st{据说是}经典套路：
  
  待定系数法，设 \(f(i)=A_i \times f(fa_i) + B_i\) \[
  \begin{split}
  f(i) &= \dfrac{1}{deg_i}\left(\sum_{v}\limits{\left(f(v) + 1\right)} + f(fa_i) + 1\right) \\\\
  &= \dfrac{1}{deg_i}\left(\sum_{v}\limits{\left(A_vf(i)+B_v + 1\right)} + f(fa_i) + 1\right) \\\\
  &= \dfrac{1}{deg_i -\sum{A_v}} f(fa_i)+\dfrac{deg_i+\sum{B_v}}{deg_i-\sum{A_v}}
  \end{split}
  \]
  所以：\(A_i =  \dfrac{1}{deg_i -\sum{A_v}}, B_i=\dfrac{deg_i+\sum{B_v}}{deg_i-\sum{A_v}}\)
  
  特殊的：对于 \(i \in T\) , \(A_i = B_i = 0\)。
  
  这里的 \(A, B\) 可以直接通过树上 dp 求出。同时，可以递推出 \(f(i)\)
  的值。
  
  设 \(F(T) = (-1)^{|T|-1}f(x)\) ,答案就是
  \(\sum_{T \subseteq S}\limits{F(T)}\)
  
  考虑到这东西是子集和变换，使用 FMT (快速莫比乌斯变换) 预处理即可。然后
  \(O(1)\) 回答。
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 87.
  
  [1] [2]
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [3] [4] [5] [6] [7] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (7 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 87.
  
  [1] [2]
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [3] [4] [5] [6] [7] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (7 pages).
  Transcript written on .../input.log.