【ZSROI R1-D 完美皮肤】
前言：为了方便描述，在本题目里面的 Ai,BiA_i,B_iAi ,Bi 在本篇题解内会转为小写 ai,bia_i,b_iai ,bi 。
30pts:30pts:30pts:
n≤19n\le 19n≤19，可以猜出大概是一个 O(2nn)O(2^nn)O(2nn) 的算法。
定义 fSf_SfS 表示待选择集合为 SSS 时还需要的天数期望。
有边界 f∅=0f_{\emptyset}=0f∅ =0（即空集）
考虑转移 fSf_SfS ，记 A=∑i∈SaiA=\sum_{i\in S} a_iA=∑i∈S ai ，B=∑i∈SbiB=\sum_{i\in S} b_iB=∑i∈S bi ，有：
fS=A−BA×(fS+1)+∑kbkA×(fS∖{k}+1)f_S=\frac{A-B}{A} \times (f_S+1) +\sum_k \frac{b_k}{A}\times (f_{S \setminus \{k\}}+1) fS =AA−B ×(fS +1)+k∑ Abk ×(fS∖{k} +1)
解释一下：有 A−BA\frac{A-B}{A}AA−B 的概率没有选到目标，有 bkA\frac{b_k}{A}Abk 的概率选到 kkk 的目标。
继续转移：
fS=A−BA×fS+A−BA+BA+∑kbkA×fS∖{k}f_S=\frac{A-B}{A} \times f_S + \frac{A-B}{A} + \frac{B}{A} + \sum_k \frac{b_k}{A}\times f_{S \setminus \{k\}} fS =AA−B ×fS +AA−B +AB +k∑ Abk ×fS∖{k}
BAfS=1+∑kbkA×fS∖{k}\frac{B}{A} f_S=1+\sum_k \frac{b_k}{A}\times f_{S \setminus \{k\}} AB fS =1+k∑ Abk ×fS∖{k}
fS=AB+∑kbkB×fS∖{k}f_S=\frac{A}{B}+\sum_k \frac{b_k}{B} \times f_{S \setminus \{k\}} fS =BA +k∑ Bbk ×fS∖{k}
解毕，转移即可。
时间复杂度：O(2NN)O(2^NN)O(2NN)
100pts:100pts:100pts:
结论：fS=∑i∈Saibif_S=\sum_{i\in S} \frac{a_i}{b_i}fS =∑i∈S bi ai
证明：首先该结论对于边界 f∅f_{\emptyset}f∅ 成立。
用归纳法，令 t=∑i∈Saibit=\sum_{i\in{S}}\frac{a_i}{b_i}t=∑i∈S bi ai ，有 fS∖{k}=t−akbkf_{S \setminus \{k\}}=t-\frac{a_k}{b_k}fS∖{k} =t−bk ak ，推得：
fS=AB+∑kbkB×fS∖{k}=AB+∑kbkB×(t−akbk)=tf_S=\frac{A}{B}+\sum_k\frac{b_k}{B}\times f_{S \setminus \{k\}} =\frac{A}{B}+\sum_k\frac{b_k}{B}\times(t-\frac{a_k}{b_k})=t fS =BA +k∑ Bbk ×fS∖{k} =BA +k∑ Bbk ×(t−bk ak )=t
归纳完成，答案为 ∑i=1naibi\sum_{i=1}^n \frac{a_i}{b_i}∑i=1n bi ai
时间复杂度：O(N)O(N)O(N)
