- 根据期望的线性性，我们设 \(E_i,P_i\) 分别表示第 \(i\) 张卡牌期望造成伤害和第 \(i\) 张卡牌被选择的概率。我们可以知道：
\[\begin{align}
Ans
&= \sum\limits_{i=1}^{n} E_i \\
&= \sum\limits_{i=1}^{n} P_i d_i \\
\end{align}
\]
- 因此我们只需要考虑对于每一张卡牌怎么求出 \(P_i\)
- 我们发现如果第 \(i\) 张卡牌被考虑了 \(j\) 次，则他至少被选择一次的概率为 \(1-(1-p_i)^j\) ，即总的概率 \(-\) 不会被选的概率
- 我们把原问题画成一个表格，其中第 \(i\) 行表示第 \(i\) 轮，第 \(j\) 列表示第 \(j\) 张牌。我们考虑竖着 dp 这个问题，因为横着 dp 我们是不好记录前若干轮的状态的，而题目有一个比较重要的性质：如果技能发动，则对敌方造成 \(d_i\) 点伤害，并结束这一轮。因此我们只需要考虑前 \(i\) 张牌在 \(r\) 轮中被选择了多少张即可
- 设计状态：设 \(dp_{i,j}\) 表示前 \(i\) 张牌在 \(r\) 轮种选了 \(j\) 张的概率
- 初始化： \(dp_{i,j} \leftarrow 0, dp_{0,0} \leftarrow 1\)
- 转移：\(dp_{i,j} \leftarrow dp_{i-1,j} \times (1-p_i)^{r-j} + dp_{i-1,j-1} \times (1-(1-p_i)^{r-j+1})\)
- 统计答案： \(P_i = \sum\limits_{j=0}^{r} dp_{i-1,j} \times (1-p_i)^{r-j}\)
- 最终复杂度 \(O(Tnr)\)