有 $n - 1$ 个人和 $1$ 个吸血鬼，每天都会有两个人相遇，如果一个是人一个是吸血鬼，那么人有 $p$ 的概率变成吸血鬼， 问你所有人都变成吸血鬼的期望天数。

思路：

令 $dp[i]$ 表示 $i$ 个吸血鬼，$n - i$ 个人类时的期望值。

首先 $dp[n]$ 是 $0.0$；

1. 有人变成了吸血鬼：$P_1 = ((C^{1}_{i} \times C^{1}_{n-i}) \div C^{2}_{n}) \times p$

2. 没有人变成吸血鬼：$P_2 = 1 - P_1$

所以 $dp[i] = P_1 \times dp[i + 1] + P_2 \times dp[i] + 1$

$dp[i] = P_1 \times dp[i + 1] + (1 - P_1) \times dp[i] + 1$

$dp[i] = P_1 \times dp[i + 1] + dp[i] - dp[i] \times P_1 + 1$

$0 = P_1 \times dp[i + 1] - dp[i] \times P_1 +1$

$0 = P_1 \times (dp[i + 1] - dp[i] + \dfrac{1}{P_1})$

两边同时除以 $P_1$，得：

$0 = dp[i + 1] -dp[i] +\dfrac{1}{P_1}$

即 $dp[i] = dp[i + 1] + \dfrac{1}{P_1}$

然后就不会算 $\dfrac{1}{P_1}$ 了 $(1 \leq n \leq 100000)$ 。

上网搜了搜题解，发现给了一个式子：

$P[i] = i \times (n - i) \div (n \times (n-1)\div2)$

可是不知道怎么推。。

求大佬解答orz