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