零食派对

吃掉每块零食的概率与前缀和

设 $X_i$ 为是否吃掉第 $i$ 块零食的指示变量，吃掉的概率为 $e_i$。由期望的线性性，区间 $[l,r]$ 的答案为

$$\mathbb{E}\left[\sum_{i=l}^{r}X_i\right]=\sum_{i=l}^{r}\mathbb{E}[X_i]=\sum_{i=l}^{r}e_i.$$

不同零食被吃掉的事件不必独立。所有询问对应同一个完整过程，因此只需从头计算一次全部 $e_i$。

饱腹感分布 DP

令 $dp[s]$ 表示查看当前零食前饱腹感为 $s$ 的概率。初始 $dp[0]=1$，其余为零。对于第 $i$ 块零食，定义

$$q_s=\max(0,p_i-0.05s),$$

则

$$e_i=\sum_{s=0}^{20}dp[s]q_s.$$

将下一步分布 $ndp$ 清零，对每个 $s$ 进行

$$ndp[\min(20,s+1)]\mathrel{+}=dp[s]q_s,$$ $$ndp[\max(0,s-1)]\mathrel{+}=dp[s](1-q_s).$$

随后用 $ndp$ 替换 $dp$。不能原地更新，否则会将当前零食产生的结果再次当成当前步骤的输入。

保存 $F_0=0$、$F_i=F_{i-1}+e_i$，每个答案就是 。不能在询问的左端点重新初始化分布。一般也不能只保存平均饱腹感：概率在零处的截断和饱腹感零的边界，使后续行为依赖完整分布，而非仅依赖平均值。

正确性与复杂度

假设当前 $dp$ 是正确分布。两类转移分别乘上给定的条件概率，将所有结果完整划分为吃与不吃，并送到正确的下一饱腹感状态。因此 $ndp$ 是正确的下一分布，全概率公式也给出正确的 $e_i$。初始分布正确，故由归纳可知所有概率正确，再由期望线性性和前缀和得到所有答案。

饱腹感只有 21 个状态，时间复杂度为 $O(21N+Q)$，包含前缀和的空间复杂度为 $O(N)$。询问读入后即可作答，无须保存所有询问。

小规模与数值处理

子任务 1 中 $N\leq8$，可以递归枚举全部吃或不吃的结果序列。令 $c_i=100p_i$，每一步吃掉的概率分子为 $$，不吃的分子为 100 减去该值。所有结果具有共同分母 。计算每个结果的分子乘积，并将其加入该结果中吃掉的每块零食的分子总和。时间为 ，空间为 。

此时分母不超过 $10^{16}$，期望前缀和的分子不超过 $8\cdot10^{16}$，可用有符号 64 位整数精确计算。完整限制下不要构造巨大的精确分母，而应使用足够精确的浮点数。主解法将输入读成整数 $c_i$，用 long double 计算 ，并输出小数点后 15 位。期望数量始终在零与区间长度之间。

检查器只接受有限数值，并对选手值 $a$、参考值 $b$ 检查 $|a-b|\leq10^{-6}\max(1,|b|)$，这与规定的绝对误差或相对误差条件等价。

独立验证

另一份实现维护累积分布 $C_j=P(S\leq j)$，而非逐状态概率。对 $j<20$，有

$$C'_j=C_j-P(S=j)q_j+P(S=j+1)(1-q_{j+1}),\qquad C'_{20}=1.$$

此外 $q_{20}=0$，只有在饱腹感零时不吃，才会阻止通常的减一变化。因此

$$e_i=\frac{\mathbb{E}[S']-\mathbb{E}[S]+1-P(S=0)(1-p_i)}{2}.$$

通过 $\mathbb{E}[S]=\sum_{j=0}^{19}(1-C_j)$ 求平均值。全部数据均与该累积分布及平均变化实现交叉比较，小规模还与整数分子的精确枚举结果比较。

Solution written by GPT6