問題文
cookie 工厂具有以下属性。
- 生成普通 cookie 和金色 cookie。生成的时间是整数秒。
- 普通 cookie 是 1 每秒 仅生成 1 块。
- 金色 cookie 与生成常规 cookie 的条件不同。 1 每秒概率 P 仅出现 1 。
- 点击的金色饼干消失,N 脱离街道的影响 产生 1 效果。
- 効果 i 是概率 q_i 以及下一秒生成的正常 cookie。 t_i 次,正常生成的cookie数量 x_i 相乘。
- 上述效果重叠。比如某秒的效果 如果继续 i 是 2 回、効果 j 是 1 次,则该秒生成的cookie数量为 x_i^2*x_j 。
| 秒 | 0 | 1 | 2 | 3 | 4 | 5 |
| 枚数 | 1 | 2 | 6 | 2 | 1 | 1 |
高桥喜欢计算。 如果您从0 秒开始并单击出现的所有金色饼干,
T-1 求第二次 cookie 生成结束时生成的正常 cookie 总数的期望值。
入力
T N P q_1 x_1 t_1 q_2 x_2 t_2 : q_N x_N t_N
- 1 行是一个整数,表示生成cookie的时间 T\ (1≦T≦100,000),一个整数,表示 cookie 的效果类型。 N\ (1≦N≦10,000),金色饼干出现的概率 P\ (0≦P≦1) 由半角空格分隔。
- 2 从行 N 线通过点击金色饼干发生 代表第 i 个效果。效果出现的概率 q_i\ (0≦q_i≦1),表示效果乘数的整数 x_i\ (1≦x_i≦1,000),表示效果持续时间的整数 t_i\ (1≦t_i≦100,000) 用空格分隔。
- q_i 的总和是 1 变为。 给定了
- 正确的输出是 它不能超过 10^{100} 。
- 给出的所有十进制输入最多为 最多只有 6 。
出力
请在输出末尾添加换行符。
输出至少有一个绝对误差或相对误差。 10^{-3} 或更少是可以接受的。
入力例 1
10 2 0.5 0.5 10 1 0.5 2 1
出力例 1
32.5
- 第一 1 秒必须是 将生成 1 cookie。
- 2 从第二个开始, 生成10 cookie 的概率为 25%、2 cookie 的概率为25%所以平均每秒 3.5 cookie。
入力例 2
100000 3 0.01 0.48175 7 77 0.033325 777 13 0.484925 1 100
出力例 2
16540797.4844572
入力例 3
300 1 1 1 2 1000
出力例 3
2037035976334490000000000000000000000000000000000000000000000000000000000000000000000000000
- 输出不得采用指数表示法。另请注意,存在一定的误差范围。