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

[problemUrl]: https://atcoder.jp/contests/arc015/tasks/arc015_4 高橋くんのお仕事は、クッキー工場で金色のクッキーをクリックするだけの簡単なお仕事である。 クッキー工場は次の性質を持っている。 - 通常のクッキーと金色のクッキーが生成される。生成される時刻は整数秒である。 - 通常のクッキーは $ 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 $ 倍の効果を発動したとき、生成される通常のクッキーの枚数は、 秒$ 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 $ 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 $ となる。 11. 正しい出力が $ 10^{100} $ を上回ることはない。 12. 与えられる小数の入力は全て、多くても小数第 $ 6 $ 位までしか存在しない。 $ T-1 $ 秒目のクッキー生成が終わった時点で、生成された通常のクッキーの総数の期待値を1行で出力せよ。 なお、出力の最後には改行をいれること。 出力は絶対誤差あるいは相対誤差の少なくとも片方が $ 10^{-3} $ 以下であれば許容される。 ```

10 2 0.5
0.5 10 1
0.5 2 1
```

 ```
32.5
```

- 最初の $ 1 $ 秒は、必ず $ 1 $ 枚のクッキーが生成されます。
- $ 2 $ 秒目からは、$ 10 $ 枚のクッキーが生成される確率が $ 25% $、$ 2 $ 枚のクッキーが生成される確率が$ 25% $なので、平均して毎秒 $ 3.5 $ 枚のクッキーが生成されます。
 
```
100000 3 0.01
0.48175 7 77
0.033325 777 13
0.484925 1 100
```

 ```
16540797.4844572
```

 ```
300 1 1
1 2 1000
```

 ```
2037035976334490000000000000000000000000000000000000000000000000000000000000000000000000000
```

- 出力は指数表記にしてはいけません。誤差が許容される点にも注意してください。
                            

N/A

N/A