Base cases : E(0) = 0, E(1) = 1

Use dynamic programming, store the expected value of nth move in dp[n]

Also dp[0] = 0 and dp[1] = 1 as base conditions

Iterate from 2 to n and update dp[n] as

dp[n] = p * (1 + dp[N-1]) + (1 - p) * (1 + dp[N-2])

I used an iterative approach like this:

Basically, there can be 2 final states, 0 or -1 after the moves, and the moves can be like (222...111...), so we can just fix number of 2-moves (say m2), and calculate the 1-moves (say m1), then the expected value for 0-state would be:

We can then iterate over counts of 2, and add this up. Similarly, for -1 state, we can calculate it like N-1 to 0, and then append a 2-move.

Submission would make it clearer: https://atcoder.jp/contests/abc280/submissions/36977527

For a component $$$C$$$, if there is a non-zero-sum cycle $$$cyc$$$ in it, we know there will be a positive-sum cycle, i.e., either $$$cyc$$$ or its reverse. So, for any two nodes $$$x$$$ and $$$y$$$ in $$$C$$$, $$$x$$$ can go to $$$cyc$$$ and increase its score infinitely then go to $$$y$$$.

Proof that ignoring back-edges that cause a cycle sum to be $$$0$$$ is equivalent to checking that there are no non-zero-sum cycles:

Consider one of such edges $$$e$$$ with score $$$w$$$ connecting nodes $$$x$$$ and $$$y$$$, we know that $$$y$$$ goes to $$$x$$$ through a sequence of edges $$$S$$$ with total score of $$$-w$$$ then goes from $$$x$$$ to $$$y$$$ through $$$e$$$. This means we can go from $$$x$$$ to $$$y$$$ through reverse of $$$S$$$ with a total score of $$$w$$$. Which means we can remove $$$e$$$ as it can be replaced by reverse of $$$S$$$.

So, after removing all back-edges, we are sure all path scores in the original graph have equivalents in the reduced graph, i.e., only $$$w$$$ from $$$x$$$ to $$$y$$$ and only $$$-w$$$ from $$$y$$$ to $$$x$$$.