D - きんいろクッキー Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋くんのお仕事は、クッキー工場で金色のクッキーをクリックするだけの簡単なお仕事である。
クッキー工場は次の性質を持っている。
  • 通常のクッキーと金色のクッキーが生成される。生成される時刻は整数秒である。
  • 通常のクッキーは 1 秒につき 1 枚だけ生成される。
  • 金色のクッキーは、通常のクッキーの生成条件とは別に 1 秒につき確率 P で 1 枚だけ出現する。
  • クリックされた金色のクッキーは消滅し、N 通りの効果のうち 1 個の効果をもたらす。
  • 効果 i は確率 q_i で起こり、その次の秒に生成される通常のクッキーから t_i 回、生成される通常のクッキーの個数を x_i 倍する。
  • 上記の効果は重複する。たとえば、ある秒で効果 i が 2 回、効果 j が 1 回継続している場合、その秒でのクッキーの生成数は x_i^2*x_j 個となる。
たとえば、開始 0 秒後にクリックした金色のクッキーが持続時間 3 秒、倍率 2 倍の効果を発動し、1 秒後にクリックした金色のクッキーが持続時間 1 秒、倍率 3 倍の効果を発動したとき、生成される通常のクッキーの枚数は、
秒012345
枚数126211
となる。
高橋君は皮算用が好きである。0 秒からはじめて、出現する金色のクッキーをすべて出現時にクリックした場合、
T-1 秒目のクッキー生成が終わった時点で、生成された通常のクッキーの総数の期待値を求めよ。

入力

入力は以下の形式で標準入力から与えられる。 
T N P
q_1 x_1 t_1
q_2 x_2 t_2
:
q_N x_N t_N
  1. 1 行目は、クッキーを生成する時間を表す整数 T\ (1≦T≦100,000)、クッキーが持つ効果の種類を表す整数 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 秒目のクッキー生成が終わった時点で、生成された通常のクッキーの総数の期待値を1行で出力せよ。
なお、出力の最後には改行をいれること。
出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{-3} 以下であれば許容される。

入力例 1

10 2 0.5
0.5 10 1
0.5 2 1

出力例 1

32.5
  • 最初の 1 秒は、必ず 1 枚のクッキーが生成されます。
  • 2 秒目からは、10 枚のクッキーが生成される確率が 25%、2 枚のクッキーが生成される確率が25%なので、平均して毎秒 3.5 枚のクッキーが生成されます。

入力例 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
  • 出力は指数表記にしてはいけません。誤差が許容される点にも注意してください。