min-max 容斥

min-max 容斥Max(S)∑T⊂S,T≠ϕ(−1)∣T∣−1Min(T)Max(S)\sum\limits_{T\subset S,T\neq \phi}(-1)^{|T|-1}Min(T)Max(S)T⊂S,Tϕ∑​(−1)∣T∣−1Min(T)kMax(S)∑T⊂S,∣T∣≥k(−1)∣T∣−k(∣T∣−1k−1)Min(T)kMax(S)\sum\limits_{T\subset S,|T|\ge k}(-1)^{|T|-k}{|T|-1\choose k-1}Min(T)kMax(S)T⊂S,∣T∣≥k∑​(−1)∣T∣−k(k−1∣T∣−1​)Min(T)[hdu4336]Card Collectornnn个物品每次操作有pip_ipi​的概率选中第iii个物品∑pi1\sum{p_i}1∑pi​1求把所有物品选中至少一遍的期望次数。n≤20n\le 20n≤20Min(S)1∑i∈SpiMin(S)\frac 1{\sum\limits_{i\in S}p_i}Min(S)i∈S∑​pi​1​[bzoj4036]按位或[0,2n−1][0,2^n-1][0,2n−1]中的整数每次操作有pip_ipi​的概率选中数iii∑pi1\sum{p_i}1∑pi​1求选中的数的或为2n−12^n-12n−1的期望次数。n≤20n\le 20n≤20Min(S)1∑i∈SpiMin(S)\frac 1{\sum\limits_{i\in S}p_i}Min(S)i∈S∑​pi​1​[luogu4707]重返现世nnn个物品每次操作有pi/mp_i/mpi​/m的概率选中第iii个物品∑pim\sum{p_i}m∑pi​m求选中至少k个物品的期望次数。n≤1000,∣n−k∣≤10,m≤1000n\le 1000,|n-k|\le 10 , m\le 1000n≤1000,∣n−k∣≤10,m≤1000Min(S)1∑i∈SpiMin(S)\frac 1{\sum\limits_{i\in S}p_i}Min(S)i∈S∑​pi​1​E(kMax(S))∑T⊂S,∣T∣≥k(−1)∣T∣−k(∣T∣−1k−1)E(Min(T))E(kMax(S))\sum\limits_{T\subset S,|T|\ge k}(-1)^{|T|-k}{|T|-1\choose k-1}E(Min(T))E(kMax(S))T⊂S,∣T∣≥k∑​(−1)∣T∣−k(k−1∣T∣−1​)E(Min(T))由于有∣n−k∣≤10,m≤1000|n-k|\le 10, m \le 1000∣n−k∣≤10,m≤1000可以枚举每对k,E(Min(T))k,E(Min(T))k,E(Min(T))对答案的贡献。令f(i,j,k)f(i,j,k)f(i,j,k)表示前i个数pi和为j且公式中的k为k时的答案f(i,j,k)∑T⊂S,∑i∈Tpij(−1)∣T∣−k(∣T∣−1k−1)f(i,j,k)\sum\limits_{T\subset S,\sum_{i \in T}{p_i}j}(-1)^{|T|-k}{|T|-1\choose k-1}f(i,j,k)T⊂S,∑i∈T​pi​j∑​(−1)∣T∣−k(k−1∣T∣−1​)则f(i,j,k)f(i−1,j,k)(−1)∗(f(i−1,j−pi,k)−f(i−1,j−pi,k−1))f(i,j,k)f(i-1,j,k)(-1)*(f(i-1,j-p_i,k)-f(i-1,j-p_i,k-1))f(i,j,k)f(i−1,j,k)(−1)∗(f(i−1,j−pi​,k)−f(i−1,j−pi​,k−1))LOJ 2542「PKUWC2018」随机游走给定一棵 n 个结点的树你从点 x 出发每次等概率随机选择一条与所在点相邻的边走过去。有 Q 次询问每次询问给定一个集合 S求如果从 x 出发一直随机游走直到点集 S 中所有点都至少经过一次的话期望游走几步对于 100% 的数据有1≤n≤181≤Q≤50001≤k≤n1\leq n\leq 181\leq Q\leq 50001\leq k\leq n1≤n≤181≤Q≤50001≤k≤n。考虑对于一个点集S第一次经过的期望时间f(x,S)为x∈S,f(x,S)0x \in S ,f(x,S)0x∈S,f(x,S)0x∉S,f(x,S)1/degu∗∑v,(v,x)∈Ef(v,S)1x \notin S ,f(x,S) 1/deg_u*\sum_{v,(v,x)\in E}f(v,S)1x∈/S,f(x,S)1/degu​∗∑v,(v,x)∈E​f(v,S)1f[i][S]1de[i]∑(i,j)∈E(f[j][S−{i}]1)f[i][S] \frac{1}{de[i]}\sum\limits_{(i,j) \in E}(f[j][S - \{i\}] 1)f[i][S]de[i]1​(i,j)∈E∑​(f[j][S−{i}]1)f[i]1de[i]∑(i,j)∈E(f[j][S]1)1d[i]f[fa[i]]1de[i]∑ifa[j](Ajf[i]Bj1)1d[i]−∑ifa[j]Ajf[fa[i]]∑ifa[j](Bj1)1d[i]−∑ifa[j]Aj\begin{aligned} f[i] \frac{1}{de[i]}\sum\limits_{(i,j) \in E}(f[j][S] 1) \\ \frac{1}{d[i]}f[fa[i]] \frac{1}{de[i]}\sum_{i fa[j]}(A_jf[i] B_j 1) \\ \frac{1}{d[i] - \sum_{i fa[j]}A_j}f[fa[i]] \frac{\sum_{i fa[j]}(B_j 1) 1}{d[i] - \sum_{i fa[j]}A_j} \end{aligned}f[i]​de[i]1​(i,j)∈E∑​(f[j][S]1)d[i]1​f[fa[i]]de[i]1​ifa[j]∑​(Aj​f[i]Bj​1)d[i]−∑ifa[j]​Aj​1​f[fa[i]]d[i]−∑ifa[j]​Aj​∑ifa[j]​(Bj​1)1​​转成树上dp