← 返回题目列表

AtCoder · arc015_4

D. 金罗饼干

中文机器翻译题面 查看原题

問題文

高桥君的工作就像在饼干工厂点击金色饼干一样简单。
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 秒后点击的金色 cookie 是持续时间 3 秒、倍率 2 激活双重效果,1 秒后点击的金色 cookie 是持续时间 1 秒、倍率 3 激活双重效果时,正常生成的cookie数量为:
秒012345
枚数126211
变为。 给定了
高桥喜欢计算。 如果您从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. 1 行是一个整数,表示生成cookie的时间 T\ (1≦T≦100,000),一个整数,表示 cookie 的效果类型。 N\ (1≦N≦10,000),金色饼干出现的概率 P\ (0≦P≦1) 由半角空格分隔。
  2. 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 变为。 给定了
  3. 正确的输出是 它不能超过 10^{100} 。
  4. 给出的所有十进制输入最多为 最多只有 6 。

出力

T-1 当第二次cookie生成完成时,输出一行中生成的正常cookie总数的期望值。
请在输出末尾添加换行符。
输出至少有一个绝对误差或相对误差。 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
  • 输出不得采用指数表示法。另请注意,存在一定的误差范围。