题面
题解
设 (p_i) 是概率，也就是题目中的 (frac {p_i}{sum p})。
设 (F(x)) 表示一直按，第 (n) 次到达目标状态的概率 EGF，于是：
[F(x) = prod_{i=1}^n frac{e^{p_ix} + (-1)^{s_i} e^{-p_ix}} 2
]
设 (G(x)) 表示按 (n) 次回到初始状态的 EGF，同理有：
[G(x) = prod_{i=1}^n frac {e^{p_ix}+e^{-p_ix}}2
]
然后设 (f(x), g(x)) 分别对应 (F(x), G(x)) 的普通型生成函数。
设 (h(x)) 表示第一次到达目标状态的概率生成函数，那么 (hg = f)，即 (h = g / f)，且 (h'(1)) 就是所求的答案。
设 (F(x) = sum_i a_i e^{ix})，那么 (f(x) = sum_i frac {a_i}{1-ix})。可以用背包求出 (F) 进而求出 (f)。
然后计算 (h = f / g)，发现 (f) 和 (g) 中均有 (1 - x) 项导致不能直接计算，所以上下同乘 (1 - x)。
发现 (((1 - x) f)(1) = ((1 - x) g)(1) = 1)，所以通过除法的求导法则，(h' = ((1 - x) f)' - ((1 - x) g)')。
那么最后一个问题就是 ((1 - x) f) 的导数怎么算，发现 ((left.frac {1 - x} {1 - ix})' ight|_{x=1} = frac 1 {i - 1})，可以轻松求得。
代码太久远了就不放了。