AT_arc015_4 [ARC015D] きんいろクッキー

高桥君的工作是在一座饼干工厂里，专门点击金色饼干。这个工厂具有以下特点： - 每秒钟会产生普通饼干和金色饼干，生产的时间是整数秒。 - 正常情况下，每秒会生成 1 块普通饼干。 - 每秒还可能以概率 $P$ 生成 1 块金色饼干。 - 当金色饼干被点击时，它会消失，并触发一种随机效果。 - 共有 $N$ 种效果可以随机触发。对于每种效果 $i$，其出现概率为 $q_i$。当效果触发时，会在之后的 $t_i$ 秒内，使正常生成的饼干数量增加 $x_i$ 倍。 - 效果可以叠加。例如，若在同一秒内，效果 $i$ 出现了两次，效果 $j$ 出现了一次，则该秒生成饼干的总数为 $x_i^2 \times x_j$。 举个例子：在第 $0$ 秒点击的金色饼干具有持续 $3$ 秒、倍率为 $2$ 的效果，而在第 $1$ 秒点击的金色饼干具有持续 $1$ 秒、倍率为 $3$ 的效果，那么生成的普通饼干数量如下： | 时间（秒） | 0 | 1 | 2 | 3 | 4 | 5 | |------------|---|---|---|---|---|---| | 饼干数量 | 1 | 2 | 6 | 2 | 1 | 1 | 现在，高桥君想知道：如果从第 $0$ 秒开始，他点击了每一个出现的金色饼干，那么在第 $T-1$ 秒结束后，生成的普通饼干总数的期望值是多少？ 输入如下格式： ``` T N P q_1 x_1 t_1 q_2 x_2 t_2 ... q_N x_N t_N ```

- 第一行包含三个整数：生成饼干的总时间 $T\ (1 \le T \le 100,000)$，效果的种类数 $N\ (1 \le N \le 10,000)$，以及金色饼干出现的概率 $P\ (0 \le P \le 1)$。 - 接下来的 $N$ 行描述每种效果： - $q_i$: 效果 $i$ 的出现概率 $(0 \le q_i \le 1)$ - $x_i$: 效果的倍率 $(1 \le x_i \le 1,000)$ - $t_i$: 效果的持续时间 $(1 \le t_i \le 100,000)$。 - 所有 $q_i$ 的总和为 $1$。

输出在第 $T-1$ 秒结束后所生成普通饼干总数的期望值。结果精确到小数点后至少三位，并确保绝对误差或相对误差不超过 $10^{-3}$。

- $1 \le T \le 100,000$ - $1 \le N \le 10,000$ - $0 \le P \le 1$ - $\sum_{i=1}^{N} q_i = 1$ - 所有输入的小数精度不超过小数点后第六位 - 正确输出不会超过 $10^{100}$ **本翻译由 AI 自动生成**