It didn't seem that hard to me. When you pick the range of minima (which seems like a good choice since we could go below zero otherwise) $$$A_{l,r}$$$, you get independent problems for $$$m = \sum_{i=1}^n \frac{i(i+1)}{2} C_i$$$ where we're counting the independent choices of $$$C_i \ge 0$$$, $$$C_n \gt 0$$$. We're summing up our DP over all choices of $$$l$$$, $$$r$$$, $$$m_{left}$$$, $$$m_{right}$$$ such that $$$N$$$ divides $$$M-m_{left}-m_{right}$$$ (since that determines the minimum value) and there are a few more observations like that $$$l$$$ and $$$r$$$ are close to the border and we can incorporate the "$$$N$$$ divides" part into our DP in the same way as we computed it.

Quite straightforward compared to A.

I just finished doing this problem, here is how I formally proved everything.

You want to prove: the expected value of the random variable $$$X$$$ which outputs the number of steps in a given operation (which is an occurrence) is the sum of probability of choosing each vertex, that is, for each vertex $$$i$$$, the probability that $$$i$$$ is in an occurrence.

$$$E[X(w)]=\sum_{w\in S}P(w)X(w)$$$, where $$$w$$$ is an occurrence and $$$S$$$ is the sample space.

Lets say that $$$w=v_1 v_2 ... v_k$$$, then $$$X(w)=k$$$, so that $$$P(w)X(w)=kP(w)=P(w)+P(w)+...+P(w)$$$.

Then for each vertex in an occurrence, we have $$$P(w)$$$ term for it in each term of the summation. If we rearrange these terms, we can get $$$E[X(w)]=\sum_{w\in S}P(w)X(w)=\sum_{w: 1 \in w} P(w)+\sum_{w: 2 \in w} P(w)+..+\sum_{w: n \in w} P(w)$$$.

(by collecting all terms of same vertices together)

So by $$$3^{rd}$$$ axiom of probability (since all occurrences are disjoint), $$$\sum_{w: j \in w} P(w)$$$ is just the probability that $$$j$$$ is in an occurrence, which is exactly what we set out to prove.