#P9790. 炸弹威力

    ID: 6414 传统题 1000ms 128MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-贡献法期望线性性期望 DP前后缀状态分解独立随机变量乘积期望

炸弹威力

题目描述

有 nn 个炸弹排成一排,第 ii 个炸弹的威力系数是 wiw_i。每个炸弹独立决定型号,第 ii 个以概率 pip_i 为会爆炸的 I 型,否则为不会爆炸的 II 型。

设 [l,r][l,r] 为一段连续且不能再向任一端延伸的 I 型炸弹。它的爆炸威力为

f(l,r)=ab(r−l)∑i=lrwi.f(l,r)=a^{b(r-l)}\sum_{i=l}^{r} w_i.

总威力是所有这样的连续段的威力之和。若没有 I 型炸弹,总威力为 00。求总威力的期望。

输入格式

第一行一个整数 nn 和两个实数 a,ba,b。第二行 nn 个整数 w1,…,wnw_1,\ldots,w_n。第三行 nn 个实数 p1,…,pnp_1,\ldots,p_n。

输出格式

输出一个实数,保留小数点后三位,表示期望爆炸威力。

样例 1

3 0.5 0.5
2 3 3
0.5 0.5 0.5
3.097

八种型号组合的概率均为 1/81/8,对应威力约为 4,3.536,5,4.243,2,3,3,04,3.536,5,4.243,2,3,3,0。

样例 2

6 0.8 0.2
1 1 4 5 1 4
0.9 0.6 0.7 0.7 0.6 0.8
10.521

原题另在下发文件中提供样例 3、4。

数据范围

1≤n≤1051\le n\le10^5,0<b,pi<10<b,p_i<1,1≤wi≤1031\le w_i\le10^3。输入小数精确到 10−210^{-2}。除明确规定 a=1a=1 的测试点外,0<a<10<a<1。

测试点 nn 上界 附加性质
1–3 18
4–10 10310^3
11 18 所有 wi=1w_i=1
12–13 10510^5
14–15 a=1a=1
16–20

原 PDF 题面