题意:
n个盒子.打开第i个盒子有p[i]概率拿到d[i]大的钻石
从第1个盒子开到第n个盒子
当开到的钻石比手里的钻石大
开到的钻石换手里的钻石
问更换钻石次数的期望是多少
(答案mod 998244353)
解法:
第i个盒子对答案贡献是 $p[i] \prod_{j=1}^i (1 - p[j])$ (d[j] > d[i])
对于第i个盒子:
前面没有钻石比它的大,才能对答案产生贡献
前面比它小的钻石,无论有没有拿到这颗小的钻石,只要现在这个盒子开到钻石,都能拿
(所以数组初始化为1)
而后面更新概率是p[i]/100
(p[i]乘以100的逆元)
钻石从大到小计算贡献
用树状数组(线段树)计算每个盒子贡献的复杂度是O(logn) (区间询问)
更新概率的复杂度也是O(logn) (单点修改)
总复杂度就是O(nlogn)
代码:
树状数组
(前缀积)
1 |
|
线段树
(区间乘积)
1 | #include <bits/stdc++.h> |
第一次觉得线段树比树状数组难QwQ