每次学容斥都感觉自己萌萌哒 !!!∑(ﾟДﾟノ)ノ
【你已经是复习了啊喂
结论
PS: Min Max可以互换位置【原因看证明
证明
考虑 第x大的元素（(x eq 1)）的容斥系数(f(x))
他会被计算(f(x)=sum_{i=0}^{x-1} (-1)^i inom{x-1}{i} =0)次 （可以二项式反演 或者直接观察杨辉三角）
而只有最大的元素会被算1次 所以正确性显然
对于(Min-Max)互换 显然就是把第x大换成第x小而已
根据期望的线性性有第二个结论 根据数论空间【诶这是什么奇怪的名字】里的运算规则可以推出第三个结论【好吧 说白了就是感性理解】
例题
其实各种容斥是相通的所以有好多题既可以二项式反演又可以(Min-Max)容斥= =
PKUWC2018随机游走
给定一棵n个结点的树，你从点x出发，每次等概率随机选择一条与所在点相邻的边走过去。
有Q次询问，每次询问给定一个集合S，求如果从x出发一直随机游走，直到点集S中所有点都至少经过一次的话，期望游走几步。
特别地，点x（即起点）视为一开始就被经过了一次。
答案对998244353取模。
(1le nle 18,1le Qle5000,1le k le n)
思路：
显然的不能再显然的(Min-Max)容斥= =
根据第二个结论 我们只需要求出(Tsubseteq S)中第一个被经过的期望时间就可以了
所以我们肯定是对于所有集合算出来最早经过的时间 直接枚举钦定的集合
然后树上高斯消元就可以了 最后容斥用FWT就能保证复杂度是(O(2^n*n))了
代码：戳我
HAOI2015 按位或
刚开始你有一个数字(0)，每一秒钟你会随机选择一个([0,2^n-1])的数字，与你手上的数字进行按位或操作。选择数字(i)的概率是(p[i])。保证(0<=p[i]<=1)，(Σp[i]=1)问期望多少秒后，你手上的数字变成(2^n-1)。
(nle 20)
思路：又是显然的(Min-Max)容斥
显然是第二个结论 考虑每一位的期望时间 就是求一个(E(Min T) = frac{1}{sum_{g oplus T eq emptyset} P[g]})
这玩意简单容斥一下就是求T的补集的子集和 FWT就可以了
代码：戳我
LOJ6102「2017 山东二轮集训 Day1」第三题
输入一个大小为(n)的集合(S)，求(lcm_{k∈S} f_k)，其中(f_k)是第(k)个Fibonacci数。
(n≤5×10^4,u≤10^6)
思路：这貌似是经典题然鹅我不会TAT
首先你需要知道(gcd(f_a,f_b)=f_{gcd(a,b)}) 证明显然就是(gcd(f_a,f_b)=gcd(f_a,f_{a-b}))就好了
显然是第三种形式
写出来(lcm(f_S)=prod_{emptyset eq T subseteq S} (-1)^{|T|-1}gcd(f_T))
既然有(gcd)那你就反演吧
设(f_n = prod_{d|n} g_d) 则有 (g_n =prod_{d|n} f_d^{mu(frac{n}{d})})
带进上边的柿子(prod_{emptyset eq T subseteq S} (prod_{d|gcd(T)} g_d)^{(-1)^{|T|-1}})
把左边的prod提到指数上 (prod g_d ^{sum_{emptyset eq T subseteq S , d|gcd(T)} (-1)^{|T|-1} })
观察指数发现有点眼熟怎么肥四 哦 就是我们用二项式反演证明过的柿子啊
设(d)指数为(S_d={ exists n in S, d|n })
所以筛一下就可以(O(nlgn))解决了
代码：戳我
UOJ449 喂鸽子
小Z是养鸽子的人。一天，小Z给鸽子们喂玉米吃。一共有n只鸽子，小Z每秒会等概率选择一只鸽子并给他一粒玉米。一只鸽子饱了当且仅当它吃了的玉米粒数量(ge k)。小Z想要你告诉他，期望多少秒之后所有的鸽子都饱了。对(998244353)取模。
(nle 50, kle 1000)
思路：
一眼(min-max)容斥 然后我们就是如何快速求(E(MinT))了
让我想起来这个题->走你 求法非常类似了
我们考虑枚举(i=|T|) 然后有(ans=sum_{i=1}^n (-1)^{i-1} inom{n}{i} frac{n}{i} f(i))
（期望每(frac{n}{i})次能搞来一个(T)中元素）
考虑求(f(i)=sum_{j=0}^{(i-1)(k-1)} g[i-1][j] (j+k) i (frac{1}{i})^{j+k} inom{j+k-1}{j})
(g[i][j])表示(i)只鸽子一共喂了(j)粒玉米 且没有鸽子吃饱的方案数
可以(O(n^2k))dp计算 dp过程中就是考虑新的一粒玉米给谁 然后减去不合法的就好了 也就是
(g[i][j] = icdot g[i][j-1] - iinom{j-1}{k-1}g[i-1][j-k])
最后总复杂度就是(O(n^2k))了
代码：戳我
扩展Min-Max容斥
考虑用min来计算第k大【是不是毒瘤！
我们刚刚的想法就是对于最大的元素 我们令它的贡献为1 否则为0
现在我们要做的就是对于第k大的元素贡献为1 否则为0
也就是(sum_{i=0}^{x-1} inom{x-1}{i}f(i) = [x==k])
根据二项式反演 有(sum_{i=0}^{n}(-1)^{n-i}inom{n}{i}[i+1==k]=f(n+1))
得到(f(n+1)=(-1)^{n-k-1}inom{n}{k-1})即(f(n)=(-1)^{n-k} inom{n-1}{k-1})
带回原式
例题
洛谷4707 重返现世
为了打开返回现世的大门，Yopilla 需要制作开启大门的钥匙。Yopilla 所在的迷失大陆有 (n) 种原料，只需要集齐任意 (k) 种，就可以开始制作。Yopilla 来到了迷失大陆的核心地域。每个单位时间，这片地域就会随机生成一种原料。每种原料被生成的概率是不同的，第 (i) 种原料被生成的概率是 (frac{p_i}{m}) 。如果 Yopilla 没有这种原料，那么就可以进行收集。Yopilla 急于知道，他收集到任意 (k) 种原料的期望时间，答案对 (998244353) 取模。
一句话题意：求全集的(k-max)
(1 le n le 1000) ，(1 le k le n, lvert n - k vert le 10) ，(0 le p_i le m, sum p = m, 1 le m le 10000)
思路：
我们就是求((n-k+1)-max)上面已经给出柿子了 我们现在就考虑怎么快速计算(Min(T))
显然暴力算(f_{i,j,k})（第i个已经选了j个概率和是k）的话是(O(nmk))级别的(dp) 我们考虑如何优化这个过程
我们换(dp)状态为(f_{j,k})（省略i那一维了）表示(f_{j,k}=sum (-1)^{i-k} inom{i-1}{k-1}Cnt_{i,j}) 其中(Cnt_{i,j})就是原来的(dp)数组 表示选了i个概率和是k
然后我们现在考虑塞进一个物品去 然后强制(k)也变大1 也就是下面这样了
(sum (-1)^{i+1-(k+1)} inom{i}{k} Cnt_{i+1,j+p[i]})
也就是集合大小增加了1 然后让k也+1
这样怎么转移呢 我们考虑把(inom{i}{k})拆成(inom{i-1}{k-1})和(inom{i}{k-1})
也就是对应(f_{k-1,j-p})和(f_{k,j-p})然后发现 这个(k-1)对应的是((-1)^{i-1-(k-1)})是对的系数 而(k)对应的是((-1)^{i-1-k})所以差了一个(-1)的系数所以最后的转移其实是(F_{k,j} = f_{k,j}+f_{k,j-p}-f_{k-1,j-p})
这样的话DP就把(k)优化到(n-k)了 最后边界问题就是(f_{i,0}(i>0))是(-1) 原因是要保证(i=k)的时候贡献是((0-(-1))=1) (i<k)的时候((-1)-(-1)=0)
最后就是逆元算贡献就可以了
好神的题.jpg
代码：戳我