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