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 Collector
nnn个物品，每次操作有pip_ipi的概率选中第iii个物品，∑pi=1\sum{p_i}=1∑pi=1，求把所有物品选中至少一遍的期望次数。n≤20n\le 20n≤20
Min(S)=1∑i∈SpiMin(S)=\frac 1{\sum\limits_{i\in S}p_i}Min(S)=i∈S∑pi1
[bzoj4036]按位或
[0,2n−1][0,2^n-1][0,2n−1]中的整数，每次操作有pip_ipi的概率选中数iii，∑pi=1\sum{p_i}=1∑pi=1，求选中的数的或为2n−12^n-12n−1的期望次数。n≤20n\le 20n≤20
Min(S)=1∑i∈SpiMin(S)=\frac 1{\sum\limits_{i\in S}p_i}Min(S)=i∈S∑pi1
[luogu4707]重返现世
nnn个物品，每次操作有pi/mp_i/mpi/m的概率选中第iii个物品，∑pi=m\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≤1000
Min(S)=1∑i∈SpiMin(S)=\frac 1{\sum\limits_{i\in S}p_i}Min(S)=i∈S∑pi1
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∈Tpi=j(−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∈Tpi=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≤18，1≤Q≤5000，1≤k≤n1\leq n\leq 18，1\leq Q\leq 5000，1\leq k\leq n1≤n≤18，1≤Q≤5000，1≤k≤n。
考虑对于一个点集S，第一次经过的期望时间f(x,S)为
x∈S,f(x,S)=0x \in S ,f(x,S)=0x∈S,f(x,S)=0
x∉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)∈Ef(v,S)+1
f[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]∑i=fa[j](Ajf[i]+Bj+1)=1d[i]−∑i=fa[j]Ajf[fa[i]]+∑i=fa[j](Bj+1)+1d[i]−∑i=fa[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]1f[fa[i]]+de[i]1i=fa[j]∑(Ajf[i]+Bj+1)=d[i]−∑i=fa[j]Aj1f[fa[i]]+d[i]−∑i=fa[j]Aj∑i=fa[j](Bj+1)+1
转成树上dp
