Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### animeFORever's blog

By animeFORever, 5 weeks ago, ,

It's one of the most beautiful dp I ever used. I'm going to explain it with an example.

Problem: 1265E

Solution: suppose $e_i$ equals the expected number of days that we stop.

$e_i = p_i * e_{i + 1} + (1 - p_i) * e_1 + 1$

$e_n = (1 - p_i) * e_1 + 1$

So how to update $e$?! :D
We will change how we show numbers. You know how we show complex numbers (if you don't learn it here), we are going to use the same idea.
Each number consists a part that is

$e_1$

and another part that is a Real number(in this problem you can change it to integer when using modulo).
We show each number with $x$ and $y$ such that the number is equal to

$x * e_1 + y$

. So we use this idea and start updating $e$ backward.
Then we will get

$e_1 = x * e_1 + y$

and now we can get

$e_1$

as an intiger.

$e_1 = y / (1 - x)$

Any other problem that uses the same idea, please mention. :D

• +100