青山网站建设,吉安购物网站制作,安徽省住房城乡建设厅门户网站,国家对网站建设的要求文章目录前言经典容斥原理广义二项式反演/广义容斥min-max 容斥所谓二项式反演#xff0c;就是对两个项的式子进行反演。 #xff08;逃#xff09;
前言
期望和容斥是我的感性二兄弟#xff01; 之前的容斥我基本也都是靠感性理解做的… 感性理解就会导致#xff1a;考…
文章目录前言经典容斥原理广义二项式反演/广义容斥min-max 容斥所谓二项式反演就是对两个项的式子进行反演。 逃
前言
期望和容斥是我的感性二兄弟 之前的容斥我基本也都是靠感性理解做的… 感性理解就会导致考场上试着写出一个式子不知道它对不对。 然后就会有写出正确式子但是不敢敲代码或者敲了半天过不去样例才明白自己的式子是错的甚至还怀疑是不是代码写挂了这样的悲剧发生我都经历过 前天差不多搞完了期望今天轮到容斥了 让我们暂时放下感性拥抱数学。
PS本篇有大量的数学语言其中的一些变换来自与对式子实质的理解直接硬看可能难以明白。建议看清楚大致思路后就按照自己的路子推一遍。因为我就是这么做的
经典容斥原理
我本来想叫它狭义容斥但似乎有点瞧不起它… 就像经典力学不叫狭义力学一样。 抽象的内容如下 假设有 kkk 个性质满足每个性质的集合分别为 A1...kA_{1...k}A1...kS{Ai∣1≤i≤k}S\{A_i|1\le i\le k\}S{Ai∣1≤i≤k}那么就有 ∣⋂i1kAi∣∑T⊆S(−1)∣T∣×∣⋂i1∣T∣Tiˉ∣|\bigcap_{i1}^k A_i|\sum_{T\subseteq S}(-1)^{|T|}\times|\bigcap_{i1}^{|T|}\bar{T_i}|∣i1⋂kAi∣T⊆S∑(−1)∣T∣×∣i1⋂∣T∣Tiˉ∣ 证明 设 GP{x∣∀Ai∈P,x∈Ai,∀Ai∉P,x∉Ai}G_P\{x|\forall A_i\in P,x\in A_i,\forall A_i\notin P,x\notin A_i\}GP{x∣∀Ai∈P,x∈Ai,∀Ai∈/P,x∈/Ai}也就是恰好满足性质集合 PPP 的元素集合。 考虑每个 GGG 集合的统计次数就有 ∑T⊆S(−1)∣T∣×∣⋂i1∣T∣Tiˉ∣∑P⊆S∣GP∣∑T∩P∅(−1)∣T∣∑P⊆S∣GP∣∑T⊆Pˉ(−1)∣T∣∑P⊆SGP[Pˉ∅]∣⋂i1kAi∣\sum_{T\subseteq S}(-1)^{|T|}\times|\bigcap_{i1}^{|T|}\bar{T_i}|\sum_{P\subseteq S}|G_P|\sum_{T\cap P\emptyset}(-1)^{|T|}\\\sum_{P\subseteq S}|G_P|\sum_{T\subseteq \bar{P}}(-1)^{|T|}\sum_{P\subseteq S}G_P[\bar{P}\emptyset]\\|\bigcap_{i1}^k A_i|T⊆S∑(−1)∣T∣×∣i1⋂∣T∣Tiˉ∣P⊆S∑∣GP∣T∩P∅∑(−1)∣T∣P⊆S∑∣GP∣T⊆Pˉ∑(−1)∣T∣P⊆S∑GP[Pˉ∅]∣i1⋂kAi∣ 证毕。
广义二项式反演/广义容斥
通常是用来进行至多和恰好之间的转化。
本人非常不喜欢广义容斥这个名字。 因为感觉它有误导性我很长时间都是按照容斥的角度硬理解但是就用容斥三个圈套来套去的那点东西把组合数说成几个里面选几个硬考虑统计次数似乎很难讲明白也许其实也可以那么理解只是我不会qwq。 我感觉还是从它的另一个叫法广义二项式反演 的角度来理解更加简单。 定义 fxf_xfx 为至少选 xxx 个元素的方案数gxg_xgx 为恰好选 xxx 个元素的方案数。 则有 fx∑ixnCixgif_x\sum_{ix}^nC_i^x g_ifxix∑nCixgi 然而通常情况下ggg 的值较难求出而 fff 的值相对简单这是就需要进行反演用 fff 求 ggg gx∑ixn(−1)i−xCixfig_x\sum_{ix}^n(-1)^{i-x}C_{i}^xf_igxix∑n(−1)i−xCixfi 证明 ∑ixn(−1)i−xCixfi\sum_{ix}^n(-1)^{i-x}C_{i}^xf_iix∑n(−1)i−xCixfi ∑ixn(−1)i−xCix∑jinCjigj\sum_{ix}^n(-1)^{i-x}C_{i}^x\sum_{ji}^nC_j^ig_jix∑n(−1)i−xCixji∑nCjigj ∑jxngj∑ixj(−1)i−xCixCji\sum_{jx}^ng_j\sum_{ix}^j(-1)^{i-x}C_i^xC_j^ijx∑ngjix∑j(−1)i−xCixCji ∑jxngj∑ixj(−1)i−xCjxCj−xi−x\sum_{jx}^ng_j\sum_{ix}^j(-1)^{i-x}C_j^xC_{j-x}^{i-x}jx∑ngjix∑j(−1)i−xCjxCj−xi−x ∑jxnCjxgj∑i0j−x(−1)iCj−xi⋅1(j−x)−i\sum_{jx}^nC_j^xg_j\sum_{i0}^{j-x}(-1)^{i}C_{j-x}^{i}\cdot1^{(j-x)-i}jx∑nCjxgji0∑j−x(−1)iCj−xi⋅1(j−x)−i ∑jxnCjxgj[jx]\sum_{jx}^nC_j^xg_j[jx]jx∑nCjxgj[jx] gxg_xgx 证毕。
类似的若 fxf_xfx 为至多选 xxx 个元素的方案数gxg_xgx 为恰好选 xxx 个元素的方案数。 则有 fx∑i0nCxigif_x\sum_{i0}^nC_x^i g_ifxi0∑nCxigi
gx∑i0x(−1)x−iCxifig_x\sum_{i0}^x(-1)^{x-i}C_{x}^if_igxi0∑x(−1)x−iCxifi 证法类似。
min-max 容斥
感觉换汤不换药。 给出式子 max(S)∑T⊂S(−1)∣T∣min(T)\max(S)\sum_{T\sub S}(-1)^{|T|}\min(T)max(S)T⊂S∑(−1)∣T∣min(T) min(S)∑T⊂S(−1)∣T∣max(T)\min(S)\sum_{T\sub S}(-1)^{|T|}\max(T)min(S)T⊂S∑(−1)∣T∣max(T) 这里只给出第一个式子的证明第二个式子的证明较为类似。 考虑最大值 max(S)\max(S)max(S)它成为最小值产生贡献当且近当 T{max(S)}T\{\max(S)\}T{max(S)}显然只会产生一次正贡献。 而对于不是最大值的元素 x∈Sx\in Sx∈S设比它大的元素的个数为 kkk那么它成为最小值产生贡献当且近当 TTT 为前 kkk 个元素的某个子集并上 {x}\{x\}{x}那么它的系数就是 ∑i0x(xi)(−1)i\sum_{i0}^x\binom{x}{i}(-1)^ii0∑x(ix)(−1)i 二项式反演一下 ∑i0x(xi)(−1)i∑i0x(xi)(−1)i(1)x−i(1−1)x0\sum_{i0}^x\binom{x}{i}(-1)^i\sum_{i0}^x\binom{x}{i}(-1)^i(1)^{x-i}(1-1)^{x}0i0∑x(ix)(−1)ii0∑x(ix)(−1)i(1)x−i(1−1)x0 所以所有不是最大值的元素的贡献都是0。 那么最后西格玛的结果就是 max(S)\max(S)max(S)。 注意这个式子当最小值不唯一的时候依然成立min(T)\min(T)min(T) 的含义就变为了所有并列最小值的和。但是所求的最大值必须唯一
