Reading the editorial of this atcoder problem agc028_b (editorial), I noticed that the solution was similar to the solution of D. Score of a Tree (editorial).
Both of those problems define a function to calculate a value based on a random initial configuration of elements. The problems then ask for the sum of values for every possible initial configuration. The editorial solutions involve calculating the expected value of the result and multiplying it by some other value (the contribution of each element or the amount of possible configurations).
My question is, how can we relate the expected value of a result to the exact sum of every possible result? Do you guys have other problems involving that technique or sources that explain it?
Thanks!
I've been hard-stuck on this for a couple of days and finally understood it after posting it to CF haha
It is actually really basic, it comes from the definition of $$$EV[X] = \sum_{x \in X} value(x) P(x)$$$.
In these problems, the probability of each event or configuration is the same ($$$\frac{1}{n!}$$$ and $$$\frac{1}{2^n}$$$ respectively). So, we can get the answer by applying the following: $$$\frac{EV[X]}{P(x)} = \sum_{x \in X} value(x)$$$.